Is the Church-Turing thesis a theorem? Conjecture? Axiom?

Question

One thing I was never clear on when taking Computational Complexity in college is whether the Church-Turing "thesis" is (or can be) proven.

Is it..

• A theorem? If so, where's the proof?
• A conjecture? If so, why isn't considered one of the great open problems? This seems even more important than P=NP
• An axiom? If so, does that mean we can study mathematical systems where the thesis is not true?

---

The wikipedia page calls it a "conjecture", but then goes on to say

it cannot be formally proven, as the concept of effective calculability is only informally defined.

A statement which makes no sense to me. If we have a proof that the "thesis" is undecidable in some system, wouldn't that make it an axiom?

Answer 1

The Church-Turing thesis is not a theorem, conjecture, or axiom. For it to be one of these, it would need to be a mathematical statement that has the potential to have a rigorous proof. It does not.

The Church-Turing thesis is, in one common formulation:

every effectively calculable function can be computed by a Turing machine.

The problem is that "effectively calculable" does not have a rigorous mathematical definition. You can give it one, and then you have a theorem, such as the following:

every general recursive function can be computed by a Turing machine,

or

every $\lambda$-definable function can be computed by a Turing machine,

but this doesn't show that there aren't other ways of effectively calculating functions that cannot be computed by a Turing machine.

The above two theorems, by the way, are what led to the proposal of the Church-Turing thesis.

Answer 2

A thesis is a statement believed to be true like a conjecture / hypothesis, i.e, something that seems to be true but is rather informal stated. You can check here https://en.wikipedia.org/wiki/Thesis_(disambiguation) I think it can help you

Answer 3

I would call it a law of nature. It is a general and fundamental description of how the universe works, that we believe (based on evidence) to be true.

For example, the Second Law of Thermodynamics states that entropy of closed systems does not increase on average. We have models of the universe in which we can prove the second law. But they are just models. One cannot prove that it is true or false about the actual universe. One can only try to find experimental evidence that refutes it, and fail. The same things are true for Church-Turing.

Another similar phenomenon also considered "laws" are things like Zipf's Law, i.e. an empirical statement about the world that seems to hold wherever we look so far.

• https://en.wikipedia.org/wiki/Scientific_law
• https://plato.stanford.edu/entries/laws-of-nature/

---

Background: the Church-Turing thesis is the statement that anything that can be computed, can be computed by a Turing machine. The Turing machine is a formal mathematical model, so what it computes is well defined. However, "anything that can be computed" is not mathematically well-defined. For any particular model of computation one proposes - lambda calculus, mu-recursive functions, etc. - one can prove whether it is equivalent in power to Turing machines or not. But since "can be computed" isn't mathematically formalizable, Church-Turing can never be formally proven or disproven.

In fact, "can be computed" must be a statement about the physics of this universe. Because we can define physics under which Church-Turing is false, e.g. hypercomputation, but this universe doesn't satisfy them. It is also probably mathematically possible to define models of computation that are more powerful than Turing machines, but where it's not clear whether they can be physically implemented. For example, it isn't obvious that the unbounded minimization operator from mu-recursive functions is physically implementable (however, it is and they turn out to be equivalent to TMs).

We could falsify Church-Turing (rather than disprove it) if we proposed a formalized mathematical model of computation and: (a) proved that it was more powerful than a Turing machine, (b) showed that it could be physically implemented consistent with known laws of physics, and ideally (c) experimentally demonstrated this implementation.

Answer 4

I asked a related question on M.SE about ten years ago with some nice responses. My favorite thing I learned from that thread is Malament-Hogarth spacetime. The upshot is that we can philosophize about physical systems that solve undecidable problems, and so the Church-Turing thesis is really an assertion about Turing Machines vs a particular kind of computation, rather than any kind of computation that is conceivable in our universe. (I definitely disagree with the claim that it is "a law of nature.")

The idea behind MH spacetime is that, to solve the halting problem, I start my computer running on an input and I program it to turn on a light if and when it halts. Then I fire it into a black hole. If I ever see it turn on the light, I know it halts; if I see it cross the event horizon without turning on the light, then since an infinite amount of time has passed from the perspective of the computer, I know it doesn't halt.

Of course there are a few things about this system that are physically implausible, including that the light gets redshifted into oblivion and so it becomes very hard to detect. But in any case, it's convincing enough to me that this thought experiment is doing something different than your run-of-the-mill Turing machine.