Kleene’s variant of the Church-Turing thesis

In 1936, Alonzo Church, Alan Turing, and Emil Post each published independent papers on the Entscheidungsproblem and introducing the lambda calculus, Turing machines, and Post-Turing machines as mathematical models of computation. A myriad of other models followed, many of them taking seemingly unrelated approaches to the computable: algebraic, combinatorial, linguistic, logical, mechanistic, etc. Of course, all of these models were shown to be equivalent in what they could compute and this great heuristic coherence lead mathematicians to formulate the Church-Turing thesis. As with many important philosophical notions, over the last three-quarters of a century, the thesis has gradually changed. In a semi-historic style, I will identify three progressively more empirical formulations with Kleene, Post, and Gandy. For this article, I will focus on the purely mathematical formulation by Kleene, and reserve the psychological and physical variants for next time.

Mathematicians and logicians begat the Church-Turing thesis, so at its inception it was a hypothesis about the Platonic world of mathematical ideas and not about the natural world. There are those that follow Russell (and to some extent Hilbert) and identify mathematics with tautologies. This view is not typically held among mathematicians, who following in the footsteps of Godel know how important it is to distinguish between the true and the provable. Here I side with Lakatos in viewing logic and formal systems as tools to verify and convince others about our intuitions of the mathematical world. Due to Godel’s incompleteness theorems and decades of subsequent results, we know that no single formal system will be a perfect lens on the world of mathematics, but we do have prefered one like ZFC.