TURING, A. M.

Computability and Lambda-Definability. (Extracted from The Journal of Sybolic Logic, Volume 2, 1937, pp.153-64.).

1937.

8vo. Bound in recent marbled boards. Title-page for volume 2 of Journal of Symbolic Logic withbound.

First edition of Turing's important paper, in which he links Kleene's recursive functions, Church's lambda-definable functions and his own computable functions and proves them to be identical.

In the appendix of his milestone-paper "On Computable Numbers" from 1936, Turing gave a short outline of a method for proving that his notion of computability is equivalent with Alonzo Church's notion of lambda-definabilty. It was not until the present article, however, that it was proved that Steven Kleene's general recursive functions, Church's lambda-definable functions and Turing's computable functions were all identical.

Kleene had already proved that every general recursive function is lambda-definable, so by showing that computability follows from lambda-definability and that general recursiveness follows from computability, Turing had ended the circle, which was a primary reason for its acceptance as a notion of "effective calculable" demanded by Hilbert's Entscheidungsproblem.

"The purpose of the present paper is to show that the computable functions introduced by the author (in "On computable numbers") are identical with the lambda-definable functions of Church and the general recursive functions due to Herbrand and Gödel and developed by Kleene." Turing wrote this paper while at Princeton studying with Church."(Hook and Norman No. 395)

Order-nr.: 25248