Comparing the Church and Turing Approaches: Two Prophetical Messages
Boris A. Trakhtenbrot · 1990
Abstract The search for a precise mathematical characterization of what “algorithm” and “computable function” should mean resulted half a century ago in the discovery of three well-known equivalent approaches. Their chronologicalorder is as follows: λ-definability (Church-Kleene, 1932-34); general recursiveness(Godel-Hetbrand, 1934) and Turing machines (1936).The type-free λ-calculus was conceived by A. Church as a foundation for logic and mathematics, but this aim failed. In spite of this failure Churchrealized that a consistent part of this calculus is a paradigm for computation· in the same way as predicate calculus is a paradigm for deduction. In 1934 he proclaimed his famous Thesis, which identifies the intuitivenotion of computable function with the formal notion of λ-definable function, but there still was some lack of consensus about this Thesis. We learn from Davis 1982 that it was only after Turing’s work that Godel accepted Church’s Thesis which had then become the Church-Turing Thesis. This is the way the miracle occurred: the essence of a process that can be carried out by purely mechanical means was understood and incarnated in precise mathematical definitions.