Lambda Calculus and Recursion Theory (Preliminary Version)

Publisher Summary This chapter discusses that the connection with recursive functions is not at all like that of the combinatory arithmetic, because the integers are taken as primitive rather than as defined. This is hardly a defect, because the aim is to construct a model out of known objects. Further, what is taken as primitive in the corresponding formal language is a very brief selection of arithmetic notions—just the ones that would naturally present themselves—and the combinators are then used to define everything else. Because no combinator is excluded, the iterators previously used to introduce integers can be studied as well in the present context. Thus, nothing has been lost, but much has been gained, because now the possibility of a real cooperation can be seen between arithmetic (and later set-theoretic) notions and those of the λ-calculus. Because the original program of relative combinatory logic could never be carried out, these connections were never clear before.