<p>I would call it a <strong>law of nature</strong>. It is a general and fundamental description of how the universe works, that we believe (based on evidence) to be true.</p>
<p>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.</p>
<p>Another similar phenomenon also considered &quot;laws&quot; are things like <a href="https://en.wikipedia.org/wiki/Zipf%27s_law" rel="nofollow noreferrer">Zipf's Law</a>, i.e. an empirical statement about the world that seems to hold wherever we look so far.</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Scientific_law" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Scientific_law</a></li>
<li><a href="https://plato.stanford.edu/entries/laws-of-nature/" rel="nofollow noreferrer">https://plato.stanford.edu/entries/laws-of-nature/</a></li>
</ul>
<hr />
<p><strong>Background:</strong> 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, &quot;anything that can be computed&quot; 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 &quot;can be computed&quot; isn't mathematically formalizable, Church-Turing can never be formally proven or disproven.</p>
<p>In fact, &quot;can be computed&quot; must be a statement about the physics of <em>this universe</em>. Because we can define physics under which Church-Turing is false, e.g. <a href="https://en.wikipedia.org/wiki/Hypercomputation" rel="nofollow noreferrer">hypercomputation</a>, 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).</p>
<p>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.</p>

CC BY-SA 4.0
2022-07-21T07:50:21.890Z
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.
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2022-07-21T18:29:52.883Z
@BlueRaja-DannyPflughoeft based on your response, you may have a misunderstanding of what the Church-Turing thesis is.
usul
CC BY-SA 4.0
2022-07-22T23:52:08.323Z
I have added some background to explain my answer further.
usul
CC BY-SA 4.0
2022-07-23T00:05:39.333Z
Re the update: I still disagree that "hypercomputation" has anything to do with physics or this universe.  You can imagine it as a thought experiment (in the same way you can imagine "a set of all sets"), but if you attempt to actually formalize it, you run into a logical inconsistency (the Halting Problem proof). Thus it's not our universe preventing hypercomputation from existing, but mathematical logic itself.
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2022-07-21T03:53:15.097Z
2022-07-22T23:51:46.210Z
2022-07-22T23:51:46.210Z
usul
<p>I asked a <a href="https://math.stackexchange.com/questions/402934/why-do-we-believe-the-church-turing-thesis">related question</a> on M.SE about ten years ago with some nice responses.  My favorite thing I learned from that thread is <a href="https://en.wikipedia.org/wiki/Malament%E2%80%93Hogarth_spacetime" rel="nofollow noreferrer">Malament-Hogarth spacetime</a>.  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 <em>a particular kind</em> of computation, rather than <em>any kind of computation</em> that is conceivable in our universe.  (I definitely disagree with the claim that it is &quot;a law of nature.&quot;)</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2022-07-22T16:35:20.900Z
2022-07-22T16:35:20.900Z
GMB
<p>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 <a href="https://en.wikipedia.org/wiki/Thesis_(disambiguation)" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Thesis_(disambiguation)</a> I think it can help you</p>

CC BY-SA 4.0
2022-07-20T08:46:21.500Z
2022-07-20T08:55:34.147Z
2022-07-20T08:55:34.147Z
Wilmer Bandres Hernández
<p>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.</p>
<p>The Church-Turing thesis is, in one common formulation:</p>
<blockquote>
<p>every effectively calculable function can be computed by a Turing machine.</p>
</blockquote>
<p>The problem is that &quot;effectively calculable&quot; does not have a rigorous mathematical definition. You can give it one, and then you have a theorem, such as the following:</p>
<blockquote>
<p>every general recursive function can be computed by a Turing machine,</p>
</blockquote>
<p>or</p>
<blockquote>
<p>every <span class="math-container">$\lambda$</span>-definable function can be computed by a Turing machine,</p>
</blockquote>
<p>but this doesn't show that there aren't other ways of effectively calculating functions that cannot be computed by a Turing machine.</p>
<p>The above two theorems, by the way, are what led to the proposal of the Church-Turing thesis.</p>

CC BY-SA 4.0
2022-07-22T10:51:28.107Z
2022-07-22T17:24:39.983Z
2022-07-22T17:24:39.983Z
Peter Shor 
<p>One thing I was never clear on when taking Computational Complexity in college is whether the Church-Turing &quot;thesis&quot; is (or can be) proven.</p>
<p>Is it..</p>
<ul>
<li><strong>A theorem?</strong>  If so, where's the proof?</li>
<li><strong>A conjecture?</strong> If so, why isn't considered one of the great open problems? This seems even more important than P=NP</li>
<li><strong>An axiom?</strong>  If so, does that mean we can study mathematical systems where the thesis is <em>not</em> true?</li>
</ul>
<hr />
<p>The <a href="https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis" rel="nofollow noreferrer">wikipedia page</a> calls it a &quot;conjecture&quot;, but then goes on to say</p>
<blockquote>
<p>it cannot be formally proven, as the concept of effective calculability is only informally defined.</p>
</blockquote>
<p>A statement which makes no sense to me.  If we have a proof that the &quot;thesis&quot; is undecidable in some system, wouldn't that make it an axiom?</p>

CC BY-SA 4.0
2022-07-20T09:05:39.753Z
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.
Denis
CC BY-SA 4.0
2022-07-20T09:09:12.027Z
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 ;)
Denis
CC BY-SA 4.0
2022-07-20T11:16:26.590Z
@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.
Martin Berger
CC BY-SA 4.0
2022-07-21T05:36:02.297Z
@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.
Emil Jeřábek
CC BY-SA 4.0
2022-07-21T07:53:43.327Z
@Denis: Is it "not a mathematical statement" because we don't know how to model all models of computation? Why are we able to quantify "all axiomatic systems" (like with Godel's Incompleteness Theorem), but not "all models of computation"? Is it just that no one's figured out how, or do we actually know for sure it's not possible?
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2022-07-21T10:55:25.147Z
@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.
Denis
CC BY-SA 4.0
2022-07-22T11:27:43.103Z
@BlueRaja: [Gödel's incompleteness theorem](https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Formal_systems:_completeness,_consistency,_and_effective_axiomatization) contains (if you write it down in enough detail) a rigorous definition of mathematical system ... a set of axioms and what can be proved from them using first-order logic. If you dropped this requirement for first-order-logic, you would no longer have a statement that could be proved rigorously.
Peter Shor 
CC BY-SA 4.0
2022-07-25T11:18:28.487Z
@EmilJeřábek The infinite tape abstraction is just an abstraction, a limit of finite state machines: Turing considered only the computation of functions on $\mathbb{N}$ and those terminate (a mistake but that's another discussion), hence use a finite tape, hence are finite state.  But we don't have interesting bounds on memory from physics, so the CTT is really saying two things: (1) what is computable if we ignore in this physical universe is what can be computed by a TM; and (2) any memory size restriction coming from physics can be modelled simply by restricting the length of the tape.
Martin Berger
<cc.complexity-theory>
Is the Church-Turing thesis a theorem? Conjecture? Axiom?
BlueRaja - Danny Pflughoeft
# Is the Church-Turing thesis a theorem? Conjecture? Axiom?

(Asked by: username_0 on 2022-07-20)

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](https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis) 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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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 ;)  
> **username_2**: @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.  
> **username_3**: @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.  
> **username_0**: @Denis: Is it "not a mathematical statement" because we don't know how to model all models of computation? Why are we able to quantify "all axiomatic systems" (like with Godel's Incompleteness Theorem), but not "all models of computation"? Is it just that no one's figured out how, or do we actually know for sure it's not possible?  
> **username_1**: @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.  
> **username_4**: @BlueRaja: [Gödel's incompleteness theorem](https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Formal_systems:_completeness,_consistency,_and_effective_axiomatization) contains (if you write it down in enough detail) a rigorous definition of mathematical system ... a set of axioms and what can be proved from them using first-order logic. If you dropped this requirement for first-order-logic, you would no longer have a statement that could be proved rigorously.  
> **username_2**: @EmilJeřábek The infinite tape abstraction is just an abstraction, a limit of finite state machines: Turing considered only the computation of functions on $\mathbb{N}$ and those terminate (a mistake but that's another discussion), hence use a finite tape, hence are finite state.  But we don't have interesting bounds on memory from physics, so the CTT is really saying two things: (1) what is computable if we ignore in this physical universe is what can be computed by a TM; and (2) any memory size restriction coming from physics can be modelled simply by restricting the length of the tape.  

---

## 4 answers

### Answer by username_4 on 2022-07-22. Score: 10 | Accepted answer

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 by username_5 on 2022-07-21. Score: 1

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](https://en.wikipedia.org/wiki/Zipf%27s_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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: @BlueRaja-DannyPflughoeft based on your response, you may have a misunderstanding of what the Church-Turing thesis is.  
> **username_5**: I have added some background to explain my answer further.  
> **username_0**: Re the update: I still disagree that "hypercomputation" has anything to do with physics or this universe.  You can imagine it as a thought experiment (in the same way you can imagine "a set of all sets"), but if you attempt to actually formalize it, you run into a logical inconsistency (the Halting Problem proof). Thus it's not our universe preventing hypercomputation from existing, but mathematical logic itself.  

---

### Answer by username_6 on 2022-07-22. Score: 0

I asked a [related question](https://math.stackexchange.com/questions/402934/why-do-we-believe-the-church-turing-thesis) on M.SE about ten years ago with some nice responses. My favorite thing I learned from that thread is [Malament-Hogarth spacetime](https://en.wikipedia.org/wiki/Malament%E2%80%93Hogarth_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.


---

### Answer by username_7 on 2022-07-20. Score: 0

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


---

