Arend Heyting Stichting
|
ABSTRACT
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 absolutely unsolvable. It has been called "the first natural law of mathematics". This talk will focus on three related topics: (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 absolute complexity lower bounds for many solvable natural problems in mathematics and computer science -- especially in number theory and algebra. (3) The relation between CT and RRT. This last point (3) gives a novel and very natural understanding of the epistemological status of CT. |