[FOM] Partial Combinatory algebras.

Thomas Forster T.Forster at dpmms.cam.ac.uk
Mon Dec 19 10:29:57 EST 2005

I asked Andy Pitts about this, and he replied:

The PhD of Andy Pitts is actually 1981 not 1980. It was preceded by
the paper of Hyland, Johnstone and Pitts

 AUTHOR={J.~M.~E.~Hyland and P.~T.~Johnstone and A.~M.~Pitts},
 TITLE={Tripos Theory},
 JOURNAL={Math.\ Proc.\ Cambridge Philos.\ Soc.},

which contains the definition as section 1.7. I see that we don't
attribute the definition to anyone else and collectively were (are?)
very careful about that sort of thing. So maybe we (truly, Martin, I
would say) invented the notion; but I don't recall thinking much of
the fact---it was just the "obvious" partial version of the more
standard notion of combinatory algebra (although subsequent work
showed there are some variations on the definition we used that one can
usefully make).


> ---------- Forwarded message ----------
> Date: Thu, 15 Dec 2005 14:45:15 +0100 (CET)
> From: Jaap van Oosten <jvoosten at math.uu.nl>
> To: fom at cs.nyu.edu
> Subject: [FOM] historical question
> Who invented partial combinatory algebras?
> I know that Sch=F6nfinkel (and later Curry) invented
> total combinatory algebras, that Feferman in his
> paper "A language and axioms for explicit mathematics"
> works with a partial application (but what he defines
> there is now called a "typed partial combinatory algebra",
> and that usually Beeson's book (1985) is credited with
> the definition (also by Beeson himself, in a recent
> paper "Lambda Logic").
> But the definition appears in the Ph.D. thesis of Andy
> Pitts (1980), 5 years earlier. Is this the first
> appearance in print of this definition?
> Jaap van Oosten=20


  URL: www.dpmms.cam.ac.uk/~tf   Tel: +44-1223-337981
  (U Cambridge); +44-20-7882-3659 (QMW) 

More information about the FOM mailing list