Kleene’s variant of the Church-Turing thesis
April 6, 2014 5 Comments
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.
Given the imperfection of every lens, it is reasonable for mathematicians to have unprovable beliefs about the mathematical world, and Kleene’s variant of the Church-Turing thesis is such a belief. Although it is a belief about mathematical structures and parts of it are expressed in formal mathematical terms, it is important to stress that it is not a conjecture. The Church-Turing thesis is not something we expect to prove or disprove (or show independent of some popular system of axioms). Thus, this belief is fundamentally different from myriad other beliefs held by mathematicians on the outcome of specific conjectures. For instance, it is perfectly rational to believe that P != NP but that belief is about the potential outcome of a specific conjecture. It is reasonable to ask for a proof of P vs NP and we known how to recognize such a proof when we see it, so we continue to search for it. Let’s decompose these thoughts a bit.
First lets talk what people tout as ‘disproofs’ of the Church-Turing thesis — hypercomputing or super-recursive algorithms (Burgin, 2006), for example. There are plenty of models of computation that are more powerful than Turing machines, and a weird myth that computer scientists ‘suppress’ them in order to promote the status quo. The easiest (and maybe historically first) super-Turing model was proposed by Turing himself: just give a Turing machine an oracle for the halting problem. Of course, even this machine won’t be able to recognize every language since it will have a halting problem of its own, and so on all the way up the Kleene-Mostowski hierarchy. If you want to recognize every one of the uncountable many possible languages then you obviously have to abandon any notion of finite descriptions for your machines, and the popular choice for cstheorists is non-uniform circuits. Both of these models are frequently studied by computer scientists, and neither shakes confidence in the CT-thesis because in both cases it is clear to the theorists that they are after a different notion than computability. It is clear that these extensions are convenient tools but are not themselves capturing the same vague intuitive notion of Platonic computability.
The easiest way to fool yourself into thinking that you are capturing the same notion while getting a hypercomputer is to introduce real numbers. Computer science is typically associated with discrete math and it is where most theorists feel most at home, but cstheorists — especially those in computational geometry — also have a careful view of real numbers (see also Blum, 2004; Braverman & Cook, 2006). Again, these models are meant as tools for understanding a different set of problems than what is meant by computation in the CT-thesis. However, if you set your model the same tasks but are sloppy in how you introduce real numbers then it is easy to sneak in hypercomputation inside these infinite objects. A typical example would be an artificial neural networks with arbitrary real numbers as its weights (Siegelmann, 1995; 1999), but everything from fancy circuits to quantum computers with non-finite generating gate sets can get the job done with such infinite precision. The transparency of these tricks makes most mathematicians believe that these models are again looking at a different part of the Platonic world of mathematical ideas. Even the proponents of these models, do not typically appeal to be violating Kleene’s variant of the CT-thesis. Instead they try to sell these models as empirically realizable and thus target Gandy’s variant that I’ll discuss further down.
Given the community’s confidence in the Church-Turing thesis, it might seem reasonable to try to prove it, and there are papers that claim to do just that (Dershowitz & Gurevich, 2008; Dershowitz & Falkovich, 2012). In fact, Copeland (2002) points out that it is a standard misconception among philosophers that Turing’s (1936) universal machine proves the Church-Turing thesis. For example, Dennett (1991) writes: “Turing had proven … that his Universal Turing machine can compute any function that any computer, with any architecture, can compute”. To understand why this is wrong requires some subtlety, so it is best to begin with a quip from Russell (1901):
Pure mathematics consists entirely of assertions to the effect that, if such and such a proposition is true of anything, then such and such another proposition is true of that thing. It is essential not to discuss whether the first proposition is really true, and not to mention what the anything is, of which it is supposed to be true … If our hypothesis is about anything, and not about some one or more particular things, then our deductions constitute mathematics. Thus mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true.
To translate into more modern language, Russell is saying that any formal derivation in mathematics is just a mapping from some specific set of axioms are basic assumptions to some desired goal. We now know that implicit in any set of axioms and rules of inference is a model of computation. Hence, any general proof of the Church-Turing thesis is just a display that a specific set of axioms are enough to be Turing complete. These basic assumptions might be very compelling, but the Turing machine was already pretty compelling, so nothing is gained beyond displaying yet another model of computation equivalent to the TM.
A variant of this is to extract a system of axioms from a physical theory and then argue that the Church-Turing thesis is true because this set of axioms is privileged in that it accurately describes nature. Of course, this has no bearing on Kleene’s variant of the Church-Turing thesis, since it is meant to talk about any ‘reasonable’ model of computation and not necessarily empirical ones. However, this technique can be used to justify that any physical model of computation has some properties, but that is Gandy’s variant of the CT-thesis and we will treat that in detail in the next post. Instead, we can get into the psychology of the question, and discuss what it means for a model to seem ‘reasonable’ to us — this gives us Post’s variant of the CT-thesis that I will also discuss in the next post. Here, my goal was to introduce the purely mathematical belief in the Church-Turing thesis and try to convince you that it is not a conjecture of which we can expect proof, but a rational belief about the Platonic world of mathematical ideas.
Blum, L. (2004). Computing over the reals: Where Turing meets Newton. Notices of the AMS, 51(9): 1024-1034.
Braverman, M., & Cook, S. (2006). Computing over the reals: Foundations for scientific computing. Notices of the AMS, 53(3): 318-329.
Burgin, M. (2006). Super-recursive algorithms. Springer.
Copeland, B.J. (2002). The Church-Turing Thesis. The Stanford Encyclopedia of Philosophy.
Dennett, D.C. (1991). Consciousness Explained. Boston: Little, Brown.
Dershowitz, N., & Gurevich, Y. (2008). A natural axiomatization of computability and proof of Church’s Thesis Bulletin of Symbolic Logic, 14 (3), 299-350 DOI: 10.2178/bsl/1231081370
Dershowitz, N., & Falkovich, E. (2012). A Formalization and Proof of the Extended Church-Turing Thesis-Extended Abstract. arXiv preprint arXiv:1207.7148.
Russell, B. (1901). Recent Work on the Principles of Mathematics. International Monthly, 4.
Siegelmann, H.T. (1995). Computation beyond the Turing limit. Science, 268(5210): 545-548.
Siegelmann. H.T. (1999). Neural networks and analog computation: beyond the Turing limit. Springer.
Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(42): 230–65.