**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?

6more comments