Theory, Evolution, and Games Group

Kleene 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…

View original post 1,392 more words