What Is Computation? And Why Turing?

This paper delves into the formation of the Church-Turing Thesis, aiming to elucidate philosophical and historical issues of the nature of computation. As a cornerstone of computer science, the Church-Turing Thesis asserts that the Turing machine is the most universal computing device. This paper explores Turing’s pivotal role in the process. The Church-Turing Thesis is a conviction supported by the fact that various computational mechanisms, including the general recursive function, $\lambda$-calculus, and the Post systems among others, have been proven mathematically equivalent. A stronger formulation of the thesis implies that “intelligence is reducible to Turing machines”, further prompting discussions on the nature of artificial intelligence. This thesis has led the theory of computation to bridge across mathematics and physics, and moreover, the most enduring dichotomy in philosophy, mind and matter.