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?
Best Answer
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.