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

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?

• The Church-Turing thesis relates the informal notion of "algorithm" with the formal notion of Turing Computability. Since half of the statement is about something that is not mathematically defined, we cannot prove anything about it (not even undecidability). As soon as you define precisely what you mean by "algorithm", you are just studying the Turing-completeness of your particular definition. Jul 20, 2022 at 9:05
• So to answer your question, it's neither of a theorem/conjecture/axiom, because it's not a mathematical statement. If you say "math is beautiful", it's also not a theorem/conjecture/axiom, even though mathematicians are convinced it's true ;) Jul 20, 2022 at 9:09
• @Denis I'd say that the CTT is a statement about physics. We do not know if it is physically true or not, but all the currently available evidence (which is empirical) points to it being true. Maybe some day somebody finds a way to execute infinitely many compute steps in finite time. Then that would falsify the CTT. Jul 20, 2022 at 11:16
• @MartinBerger If you take it as a statement of physics, it's unequivocally false. We do not have the physical resources to compute recursive functions of unrestricted growth rate, as the number of particles in the accessible part of the universe is limited. Jul 21, 2022 at 5:36
• @BlueRaja-DannyPflughoeft we can easily define models of computation stronger than Turing-computability (e.g. machines with oracles), but the point of the C-T thesis is that they are not "realistic", ie cannot be implemented in real life, which is the informal notion that escapes a mathematical definition. Jul 21, 2022 at 10:55

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.

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

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.

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.

• This is definitely incorrect. Nothing about the theory of computation assumes a particular universe. It should be unequivocally true or false (or undecidable) within a certain set of axioms, regardless of whether those axioms actually hold in a given universe. Jul 21, 2022 at 7:50
• @BlueRaja-DannyPflughoeft based on your response, you may have a misunderstanding of what the Church-Turing thesis is.
– usul
Jul 21, 2022 at 18:29