The Church-Turing thesis is often stated as follows:

And this is usually coupled with Rosser's observation that λ-calculus and recursion theory are equivalent formulations.Anything that can be computed by some means can also be computed by a Turing machine.

The problem is that phrasing, while not exactly incorrect, is not exactly right, either. It is vagueness disguised as definition. Because it is a definition, it is “correct, by definition”, but it is vague enough to admit interpretations that are absurd. Thus, if one isn't careful, one can deduce several absurdities that are “correct, by defintion”.

So what is the correct statement? The Church-Turing thesis is a statement about “effective calculability”. This is an

*intuitive*concept which tries to generalize on the idea of an

*algorithm*, or “plug and chug” math formulas, or “mechanistic” procedures like Newton's method. Many mathematicians have attempted to formalize the notion of “effective calculability”, among them Church and Turing, but also GĂ¶del, Kleene, Rosser, and Post (and many others after them, but these are the big names). A correct statement of the Church-Turing thesis is more like this:

The formal terms “computable by a Turing machine” and “λ-definable” fully capture the intuitive notion of “effectively calculable”.Naturally, the bulk of what a modern digital computer does is in fact an “effective calculation” and thus a Turing machine or λ-calculus is a very good model for what a computer can calculate. However, there are things a modern digital computer can do

*other than*calculate. These activities fall outside the scope of the Church-Turing thesis and there is no reason to believe that they would be subject to the limitations of computability.

Does anybody really know what time it is?

— Robert Lamm of Chicago

A good example of a non-computable, yet common task that a digital computer performs is to determine the current time. There is no algorithm or calculation that you can perform that will yield the current time. You simply must check a clock. Even if you somehow know the elapsed time since some event, you nonetheless have to check a clock in order to determine the beginning of the ‘epoch’ (baseline time).A whole set of non-computable quantities can be made available via reflection. Recall the definition of a Turing machine. The next state of a Turing machine is a function of the current state and the symbol on the tape under the head. It is

*not*a function of, for example, the the size of the state transition table. This is not to say that these quantities are

*unknowable*, but that they cannot be

*calculated*without introspection (certainly bounds can calculated, and certainly any machine can be instrumented or even simulated, but consider this: any Turing machine can be augmented by any number of inaccessible states. There is no way to

*calculate*the size of the state table without knowing the number of these states.) Also note, that there is nothing magic about these quantities, you can calculate to your heart's content with them

*after you obtain them*. It is obtaining them in the first place that involves something other than computation.

My mistake is this: I didn't

*specifically*and

*explicitly*state when I was referring to the informal “effective calculation” and the superset that is the informal “computing” that one can do on a modern digital computer. In other words, I applied the Church-Turing thesis to too broad a class.

Given that, I'll rephrase my Exercise 1 and see how people react:

When I phrase it that way, it sort of sounds obvious that there are going to be problems.Exercise 1:Write a program for a class of universal Turing machines that, when run,calculateswhether the machine it is on is imposing additional space complexity.

On the other hand, this is a far more satisfying rewording than

Write a portable program that is non-portable.

Hey, Joe, I sent you an e-mail at your .edu address, could you please let me know if you don't receive it? :)

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteI continue to like Hofstadter's "Church-Turing Thesis, Tautological Version", which is "Mathematics problems can only be solved by doing mathematics".

ReplyDelete