**Author’s version of a short note that appeared in the Communications of the ACM, October 2006, Vol. 49 No. 10, Pages 11-13, doi: 10.1145/1164394.1164406. The significance of this note is seen in this blogpost.**

Peter Wegner’s and Dina Goldin’s “Viewpoint” (“Principles of Problem Solving,” July 2006) provoked strong criticism from Lance Fortnow [a professor of computer science at the University of Chicago] in his “Computational Complexity” blog (weblog.fortnow.com/, dated July 14, 2006), where he notes that:

“… Wegner and Goldin misinterpret the Church-Turing thesis …”.

What Fortnow apparently overlooked was that the classical Church-Turing Thesis—expressed as a strong identity—is committed to the following strong definition of computability:

(i) **Definition**: A number-theoretic function/relation (treated as a Boolean Function), say , is effectively computable if, and only if, there is an effective method T such that, given any sequence of natural numbers , T will always compute .

The classical form of CT follows from (i):

(ii) **Classical CT**: A number-theoretic function/relation is effectively computable if, and only if, it is partial recursive/Turing-computable.

The question arises: Is such a strong commitment necessary?

The issue of whether (ii) is a definition, a theorem, or a thesis was the subject of a substantive exchange of views between Church and Gödel, neither of whom was apparently comfortable accepting (ii) as a thesis.

That their discomfort was well-founded is apparent if we replace (i) by the weaker and broader:

(iii) **Definition**: A number-theoretic function/relation, say , is effectively computable if, and only if, given any sequence of natural numbers , there is an effective method T, which may depend on , such that T will always compute .

Clearly, (i) implies (iii). Hence, by the dictum of Occam’s razor, (iii) is to be preferred as the definition of effective computability.

Moreover, the significance of (iii) over (i) is that it admits the broader possibility of number-theoretic functions/relations that are effectively computable instantiationally but not algorithmically.

The significance, and necessity, of a thesis linking effective computability with recursiveness/Turing-computability then emerges if we express CT as a weakened equivalence rather than as a strong identity:

(iv) **Instantiational CT**: A number-theoretic function/relation is effectively computable if, and only if, it is instantiationally equivalent to a partial recursive/Turing-computable function/relation.

We can then admit number-theoretic functions/relations that are effectively computable instantiationally but not algorithmically.

Are there any functions/relations that would justify (iv) intuitively?

Clearly, Turing’s Halting function and Chaitin’s Omegas are well-defined, total, number-theoretic functions that are effectively computable instantiationally but not algorithmically.

However, in the absence of (iv), we cannot link them instantiationally to recursive/Turing-computable functions.

On the other hand, if is Gödel’s undecidable arithmetical proposition, then under the reasonable assumption that if a total arithmetical relation is Turing-computable is true, then the algorithm can be converted into a proof sequence in Peano Arithmetic (an assumption vindicated by Theorem 7.1 of this 2016 paper), it can be shown that the arithmetical relation, , is effectively decidable instantiationally but not algorithmically.

This case is significant since Gödel showed (in Theorem VII of his seminal 1931 paper on undecidable arithmetical propositions) that is, indeed, instantiationally equivalent to a primitive recursive relation (which is decidable algorithmically) without appeal to any form of CT.

So Wegner’s and Goldin’s reservations about the unrestricted adoption of classical CT as definitive, and their underlying belief—that there can be effectively computable functions/relations that are not Turing-computable—ought not to be dismissed so cursorily, even though the relevance, and validity, of the particular arguments they offer in support of their belief are not obvious.

## Leave a comment

Comments feed for this article