14
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 6, 2010 at 20:02
  • 1
    $\begingroup$ The primitive recursive functions are precisely the provably recursive functions using just $\Sigma_1$ induction, but this is a theorem not a conjecture. $\endgroup$
    – François G. Dorais
    Commented Jul 6, 2010 at 20:09
  • 4
    $\begingroup$ The foundations of mathematics mailing list has members who are quite knowledgeable in history of logic. You should try asking there. $\endgroup$
    – Andrej Bauer
    Commented Jul 6, 2010 at 20:23
  • 14
    $\begingroup$ Better: let's attract them here... $\endgroup$
    – Joel David Hamkins
    Commented Jul 6, 2010 at 20:52
  • 4
    $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Commented Jul 6, 2010 at 23:15

3 Answers 3

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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). $\endgroup$
    – Antonio E. Porreca
    Commented Jul 7, 2010 at 12:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – John Stillwell
    Commented Jul 7, 2010 at 12:39
  • 2
    $\begingroup$ What did Goedel mean by saying that provability cannot be formalized, when he is widely credited with having done exactly that? $\endgroup$
    – Joel David Hamkins
    Commented Jul 7, 2010 at 19:18
  • 2
    $\begingroup$ @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." $\endgroup$
    – Timothy Chow
    Commented Feb 18, 2011 at 15:55
  • 2
    $\begingroup$ @Joshua: your statement "The proof of anything known to be true can be found in a finite number of steps" does not make sense (to me), at least if one applies to it the standards of contemporary mathematical logic. (The statement might make sense relative to some very strong philosophical standpoints and private definitions of 'proof' and 'true', yet such matters are not mathematical matters). Your statement is already problematic when you say "The proof": there is no universally agreed meaning of 'proof'; modern logic distinguishes many proof systems. $\endgroup$
    – Peter Heinig
    Commented Sep 13, 2017 at 11:40
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Way a CT-like thesis first formulated for recursive functions? I thought it was $\lambda$-calculus. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jul 7, 2010 at 1:47
1
$\begingroup$

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. http://arxiv.org/abs/quant-ph/0502072

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 http://www.math.ias.edu/~avi/BOOKS/Godel_Widgerson_Text.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .