MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Background. The Church-Turing thesis, in one of its many equivalent formulations, states that the intuitively computable arithmetical functions are exactly those computed by Turing machines.

According to Alan Turing’s classic paper On computable numbers, with an application to the Entscheidungsproblem, “intuitively computable” refers to a human computer having access to enough scratch paper to hold the intermediate results.

This thesis has been extremely successful among logicians first (including Kurt Gödel), and computer scientists later; some authors even extended it to include all functions that can be computed by any effectively realizable physical system.

Nonetheless, the Church-Turing thesis is, at least in principle, falsifiable: it is enough to describe a non Turing-computable function admitting another kind of computation procedure, executable by the above-mentioned human computer. Of course, no such function is known to exist; however, consider the following “weaker computability thesis” for the sake of argument:

Every intuitively computable arithmetical function is primitive recursive.

This is falsified by Ackermann's function, which is clearly computable (both intuitively and by a Turing machine) although not primitive recursive.

Question. Has a similar, provably weaker “computability thesis” ever been proposed before Church’s and Turing’s? As an alternative, can we reasonably argue that no such statement was ever made?

share|cite|improve this question
If you can, check out Kleene's Introduction to Metamathematics. I have a vague remembrance of his presentation of Goedel's notion of recursion, and he has some C-T discussion as well. If nothing else, you have a view from the 1950's on some of these issues. Gerhard "Ask Me About System Design" Paseman, 2010.07.06 – Gerhard Paseman Jul 6 '10 at 20:02
The primitive recursive functions are precisely the provably recursive functions using just $\Sigma_1$ induction, but this is a theorem not a conjecture. – François G. Dorais Jul 6 '10 at 20:09
The foundations of mathematics mailing list has members who are quite knowledgeable in history of logic. You should try asking there. – Andrej Bauer Jul 6 '10 at 20:23
Better: let's attract them here... – Joel David Hamkins Jul 6 '10 at 20:52
Re the first two comments: the theorem that a function on the natural numbers can be defined by what we now call primitive recursion was obtained by Dedekind 1888, although it was foreshadowed by Frege 1879. I have never seen anything that suggests Goedel believed or intended that his "rekursiv" functions gave a general account of effective calculation. – Carl Mummert Jul 6 '10 at 23:15

I think it unlikely that anyone ever proposed a weaker Church's thesis, because, as Tim Chow points out, diagonalization was known (and known to be constructive) before anyone ever contemplated a definition of computability. As early as 1907, Brouwer observed mathematics seems to be incompletable because of diagonalization, and Goedel thought that there could be no formal concept of computation until Turing's definition persuaded him otherwise in 1936. He later said that it is a "kind of miracle" that computability can be formalized while provability cannot.

Also, Post arrived at a formal definition of computability, via his concept of normal systems, in the early 1920s, though it was not published. So the full concept of computability actually arrived before weaker concepts such as primitive recursive functions.

share|cite|improve this answer
John, and also Timothy, the diagonal argument indeed prevents weaker computability theses. Then, the only remaining possibility is that someone proposed a thesis without thinking about applying diagonalisation to computable functions (though, of course, I’m entering the realm of pure speculation here). – Antonio E. Porreca Jul 7 '10 at 12:31
Antonio, yes, I think that is the only possibility. And it is unlikely because the need for a concept of computable function first arose, as far as I know, in the field of logic, where everybody was familiar with diagonalization. – John Stillwell Jul 7 '10 at 12:39
What did Goedel mean by saying that provability cannot be formalized, when he is widely credited with having done exactly that? – Joel David Hamkins Jul 7 '10 at 19:18
Joel, do you mean the formalization of computability by general recursive functions? Goedel is retrospectively given a share of the credit for this concept, because he used such functions. But it was not recognized as one of the equivalent definitions of computability until Turing machines made the concept of computability credible in 1936. (Sorry for the late reply; I missed your comment when you first made it.) – John Stillwell Feb 18 '11 at 6:46
@John: Joel was saying that Goedel is widely credited with formalizing provability (not computability). I think the answer to Joel's question is that you meant to say something like, " absolute provability cannot be formalized," where "absolute" means something like "without the need to specify a particular set of axioms that you are starting with." – Timothy Chow Feb 18 '11 at 15:55

Although your question is a historical one that really should be investigated by historical methods, there is an abstract argument that no such thesis was previously made. Namely, at first glance it seems impossible that one could characterize the intuitively computable functions, because given any such precise definition, couldn't you just diagonalize out of it to get an intuitively computable function that is not in your original class? For example, you can think of the Ackermann function as diagonalizing out of the primitive recursive functions. Surely a similar trick would apply to any other proposal? I seem to recall reading somewhere that even Goedel had this intuition at first. Thus until the recursive functions emerged as a specific candidate, it seems unlikely that anybody would have been tempted to formulate a CT-like thesis for any other class of computable functions.

share|cite|improve this answer
Way a CT-like thesis first formulated for recursive functions? I thought it was $\lambda$-calculus. – Mariano Suárez-Alvarez Jul 7 '10 at 1:47

I think you can go further and say: "effectively computable" means computable in polynomial time. These two articles might be of interest for that sort of viewpoint:

Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.

Wigderson, Avi (2010), "The Gödel Phenomena in Mathematics: A Modern View", Kurt Gödel and the Foundations of Mathematics: Horizons of Truth, Cambridge University Press

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.