Oops

I made a mistake that has lead to a lot of confusion. It is a common mistake, so I have a lot of company. To assuage the trauma to my ego, I'll point out that no one who argued with me (or, for that matter, agreed with me) identified it. Allow me to explain it and correct myself.

The Church-Turing thesis is often stated as follows:

Anything that can be computed by some means can also be computed by a Turing machine.

And this is usually coupled with Rosser's observation that λ-calculus and recursion theory are equivalent formulations.

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:

Exercise 1: Write a program for a class of universal Turing machines that, when run, calculates whether the machine it is on is imposing additional space complexity.

When I phrase it that way, it sort of sounds obvious that there are going to be problems.

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

Write a portable program that is non-portable.