Arend Heyting Stichting

## The Church-Turing Thesis and Relative Recursion - Yiannis MoschovakisABSTRACT
In contemporary terminology, the Church-Turing Thesis reads as follows: CT: Every function on the natural numbers which can be computed by
some algorithm can also be computed by a Turing machine.
It was postulated in 1936, independently (and in different but equivalent formulations) by Alonzo Church and Alan Turing, and it made it possible to prove rigorously that many natural problems in mathematics and computer science whose solution calls for an algorithm are (1) The history and applications of CT, including a brief discussion of its epistemological status---i.e., the question of what it means and why it is true. (2) The formulation and similar discussion of the Thesis on Relative Recursion: RRT: Every function on an arbitrary set A which can be compute by an algorithm from arbitrary primitives (functions and relations) on A can also be computed by a recursive (McCarthy) program from the same primitives.
RRT makes it possible to derive (3) The relation between CT and RRT. This last point (3) gives a novel and very natural understanding of the epistemological status of CT. |