<p>I'll address just the first part of your question.</p>
<p>Neither the Church–Turing Thesis nor the Extended Church–Turing Thesis is a purely mathematical or formal statement. You phrased the C–T Thesis as,  &quot;There exists no computation model capable of recognising languages that a Turing Machine cannot.&quot; I would recommend not phrasing it this way, because (as you yourself recognize), the term &quot;computation model&quot; sounds like something formal and abstract.  But it is <i>not</i> the intent of the C–T thesis to assert equality between two purely formal things.  Instead, it is a claim that a particular formal model (Turing machines) accurately captures a real-life capability that we have, namely computing.  Again, &quot;computing&quot; here is <i>not</i> a formally defined thing; it's an informal word for an activity that we physically carry out.</p>
<p>Because the C–T Thesis by its very nature is a statement about the world we physically live in, physics must come into play somehow when we seek to confirm or disconfirm it.  It is <i>not</i> a purely mathematical conjecture that we can prove or disprove purely mathematically.</p>

CC BY-SA 4.0
2020-07-26T13:59:44.193Z
2020-07-26T13:59:44.193Z
Timothy Chow
<p>The Church-Turing thesis is a kind of axiom that links an informal notion of &quot;computation by pen and paper method&quot; to a formal definition of a turing machine model. It has been proven that many different formal machine models can simulate each other and therefore satisfy the same informal notion of computation. They have been proven to be sufficiently similar that it's not usually necessary to distinguish them when discussing computability.</p>
<p>The C-T thesis is sometimes seen in proofs where the author relies on such informal notion of computation and uses the Church-Turing thesis to claim that it's possible to formalize it, usually when such formalization using primitive machine models would be unnecessarily verbose. Often proper proof for claims of proof by C-T thesis is simply to write software that implements the claimed behaviour, using any realistic computer.</p>
<p>It's also possible in certain situations to claim C-T thesis is false. That would mean either that pen-and-paper methods of computation by a human are more powerful than computers - then computers should be extended to add a new primitive operation that cannot be simulated using the existing turing machine model. Or it would mean that current models of computation using computers exceeded the level of sophistication that a human using pen-and-paper computation can perform, where you would rather attempt to improve people's ability to compute.
Since many machine models have been proven to be essentially same in the sense that they can simulate each other computationally, such improvements in computing power are unlikely for the Turing-machine model. There are several attempts to produce such more powerful machines, e.g. quantum computation, but they are usually not realistic enough to be used in practice. But such claims usually have a corresponding claim similar to the Church -Turing thesis, which attempts to formalize such approaches. Of course there are weaker and more limited machine models, which are known to be less powerful, but these can normally be simulated by the more powerful machine models.</p>
<p>Any textbook on computability can explain this in more detail. I can recommend
&quot;Hopcroft&amp;Ullman: Introduction to automata theory, languages and computation&quot;.</p>

CC BY-SA 4.0
2020-07-26T18:55:44.660Z
2020-07-26T18:55:44.660Z
Esa Pulkkinen
<p>I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't address due to space (and time to write down this answer).</p>
<hr />
<blockquote>
<p>A statement that reads, &quot;There exists no &quot;reasonable&quot; computational model capable of recognizing languages that a Turing Machine cannot&quot;</p>
</blockquote>
<p>This is essentially what the Church-Turing thesis states. It is <em>not</em> the extended Church-Turing thesis, which roughly takes the form:</p>
<blockquote>
<p>All &quot;reasonable&quot; computational models can simulate each other with polynomial overhead</p>
</blockquote>
<p>Of course, what &quot;reasonable&quot; means must itself be pinned down. For example, if you let <span class="math-container">$\mathsf{Halt}$</span> be an oracle to the halting problem, then the computational model <span class="math-container">$\mathsf{TM}^{\mathsf{Halt}}$</span> of Turing Machines equipped with halting oracles can compute strictly more than that than that of simply Turing machines.
So if <span class="math-container">$\mathsf{TM}^{\mathsf{Halt}}$</span> is viewed as &quot;reasonable&quot;, then the CT thesis is already false.</p>
<p>For this reason, &quot;reasonable&quot; is usually phrased as &quot;hypothetically realizable in the real world&quot;. As there is no proposed mechanism to create a universal <span class="math-container">$\mathsf{TM}^{\mathsf{Halt}}$</span> machine in the real world, this computational model would not be considered &quot;reasonable&quot;.</p>
<p>What does this mean for the extended CT thesis, and quantum computation? The complexity class <span class="math-container">$\mathsf{BQP}$</span> is the class of problems solvable (with bounded error) by a quantum computer efficiently. You should view it as a quantum analogue of <span class="math-container">$\mathsf{P}$</span> (more properly of <span class="math-container">$\mathsf{BPP}$</span>, or &quot;two-sided error, randomized <span class="math-container">$\mathsf{P}$</span>&quot;, but still).</p>
<p><strong>If</strong> quantum computers (which can compute arbitrary problems in <span class="math-container">$\mathsf{BQP}$</span>) are physically realizable, the extended Church-Turing thesis posits that they can only get a <em>polynomial</em> speedup over &quot;traditional&quot; models of computation. If this is the case, the extended Church-Turing thesis still holds, and quantum computing is in a certain sense &quot;more boring&quot;.</p>
<p>Preliminary evidence suggests that this is not the case though. There are a variety of problems which are known to have exponential speedups on quantum computers, famously factorization and the discrete logarithm problem via <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="noreferrer">Shor's algorithm</a>.
While these are large &quot;practical&quot; reasons for investigating quantum computation, they are actually not the theoretically most compelling reason.
Both factorization and discrete log are in <span class="math-container">$\mathsf{NP}\cap\mathsf{coNP}$</span>, and therefore unlikely to be <span class="math-container">$\mathsf{NP}$</span>-hard unless the polynomial hierarchy collapses.</p>
<p>This means that &quot;Shor's algorithm leads to an exponential speedup for factoring and discrete log&quot; isn't super interesting from a complexity theory point of view, as it's entirely consistent with current thoughts that both of these problems are actually in <span class="math-container">$\mathsf{P}$</span> (or <span class="math-container">$\mathsf{BPP}$</span>).</p>
<p>There are problems which <em>are</em> more interesting to consider though.
In particular, the <a href="https://en.wikipedia.org/wiki/Boson_sampling#The_complexity_of_the_problem" rel="noreferrer">Boson sampling</a> line of work posits a particular problem which is <span class="math-container">$\#\mathsf{P}$</span>-hard, but is in <span class="math-container">$\mathsf{BQP}$</span>.
This means that this particular problem is highly unlikely to be in <span class="math-container">$\mathsf{P}$</span>, as this would collapse the polynomial hierarchy to the third level, which is thought to be unlikely by complexity theorists.</p>
<p>So the reason that people bring quantum computing up when discussing the (extended) Church-Turing thesis is that, if sufficiently &quot;physically realized&quot;, it provides exponential speedups on practically important problems (factoring and discrete logarithm), as well as an exponential speedup on a problem which is &quot;harder than <span class="math-container">$\mathsf{NP}$</span>-complete&quot;. This would constitute a violation of the <em>extended</em> Church-Turing thesis.</p>

CC BY-SA 4.0
2020-06-29T16:19:41.873Z
Speaking of $TM^{Halt}$ as a computational model confuses me. Aren't oracles essentially $O(1)$ "get your answer free card"? Are they also considered as valid, hypothetical computation "devices"?
Novicegrammer
CC BY-SA 4.0
2020-06-29T19:55:59.197Z
@Novicegrammer Oracle turing machines are usually formalized as "standard" turing machines that have an additional "oracle tape". They can write arbitrary $x\in\{0,1\}*$ to this tape (just like with any other of their tapes). They then have an "oracle query" operation they can call. This is similar to how they have operations like "move tape head left", "move tape head right", etc. You can alternatively view Turing Machines as "uniformly generated circuits", then "oracle queries" are replaced with "oracle gates". This might be a more "concrete" way to view them, depending on your tastes.
Mark Schultz-Wu
CC BY-SA 4.0
2020-06-30T00:52:18.927Z
Just a quick nitpick re: your statement (regarding TM$^{halt}$) that _"For this reason, 'reasonable' is usually phrased as 'hypothetically realizable in the real world'"_.  IMO,  the reason has nothing to do with TM$^{halt}$ per se, or oracles at all for that matter.  IMO the reason is just that _our overall goal is to model computation as it is possible in the physical world, because we are interested in computers that can, in principle, be built and used_.  Note that, e.g., ZFC Set Theory can be used to precisely define all kinds of systems that extend far beyond what we think is computable.
Neal Young
CC BY-SA 4.0
2020-06-29T16:08:02.067Z
2020-06-29T16:08:02.067Z
Mark Schultz-Wu
<p>As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as <a href="https://cstheory.stackexchange.com/questions/7528/extended-church-turing-thesis">Extended Church-Turing Thesis</a> real-life quantum stuff is even given the time of day, because it's not relevant is it?</p>
<p>I have always thought of the C-T thesis as a statement, specifically a statement in theoretical computer science. A statement that reads, &quot;There exists no computation model capable of recognising languages that a Turing Machine cannot&quot;. Even that is a bit messy for me. Is there a formal definition for a computation model? Finite alphabet, finite states, what exactly are we talking about here?</p>
<p>Whether provable or not is another story, but it's a statement that evaluates to some logical value or another. Some people say that the C-T is a statement, some actually say it's not. I have no authority in this, so I'm left as confused as ever.</p>
<p>And if it's <em>not</em> a statement, then great! It's not a problem anymore. At least from the mathematical side of things.</p>
<p>I have a couple of what I think are misconceptions. I've taken a look at the <code>Chomsky Hierarchy</code> of grammars, and at the very top lie all the so called <code>Unrestricted Grammars</code> which have been proven to be equally expressive as Turing Machines, apparently. Now I don't even know the formal definition for <em>expressivity</em>, all I have is an intuitive understanding. CFGs are more &quot;expressive&quot; than DFAs and CSGs are more &quot;expressive&quot; than CFGs etc etc, because they can recognise all the languages the prior construction can and more. Is this actually the commonly accepted definition?</p>
<p>Now Unrestricted Grammars specifically, allow <em>production rules</em> of the form <span class="math-container">$\alpha \to \beta$</span> where <span class="math-container">$\alpha$</span> is any non-empty string and <span class="math-container">$\beta$</span> is any string. Hence, unrestricted. How on earth could a computational model compete with something that is <strong>literally unrestricted</strong>? It makes me think of the C-T thesis as trivial, &quot;<em>of course</em>&quot; it's true.</p>
<p>This left me even more confused: <a href="https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis">What would it mean to disprove Church-Turing thesis?</a></p>
<p>The accepted answer to this question starts off with:</p>
<blockquote>
<p>The Church-Turing thesis has been proved for all practical purposes.</p>
</blockquote>
<p>Why is practicality suddenly worth anything in theoretical computer science?</p>
<p>Are there like two interpretations or more of the C-T thesis, one for &quot;practical purposes&quot; and one for &quot;mathematics&quot;?</p>

CC BY-SA 4.0
2020-06-29T15:40:19.043Z
I think of the Church-Turing thesis (CT) as a hypothesis about the physical universe.  Namely, a _possible computer_ is any device that is constructible in the existing universe (consistent with the laws of physics) for manipulating information. Then CT says that any possible computer can be simulated by a TM.  I guess, historically, the fact that other proposed models of computation can be simulated by a TM gives some empirical evidence for the hypothesis. But from this perspective it is not possible to _prove_ CT (or any other assertion about the physical universe, for that matter).
Neal Young
CC BY-SA 4.0
2020-06-29T16:07:13.987Z
@NealYoung I see, so has CT always been about the physical universe?
Novicegrammer
CC BY-SA 4.0
2020-06-29T16:09:49.000Z
@Novicegrammer It (kind of) has to be, as Turing Machines equipped with a Halting problem oracle have strictly more computational power than just Turing machines. If this were a "reasonable model of computation", it would constitute a violation of the CT thesis. One way to make it "not reasonable" is to define reasonable as "hypothetically realizable in the universe".
Mark Schultz-Wu
CC BY-SA 4.0
2020-06-29T16:17:09.640Z
I see. Makes me wonder why these "oracles" are a thing and allowed to be considered as computational entities in the first place however...
Novicegrammer
CC BY-SA 4.0
2020-06-29T20:54:48.047Z
@Novicegrammer The answer to that is "because we can answer interesting questions with them". There are non-trivial results that use oracle machines. For example, given an $\mathsf{NP}$ problem instance $x\stackrel{?}{\in}L$, we can define the "witness set" $W_x$ to be the set of all witnesses to the membership $x\in L$. Many complexity classes can be phrased in terms of $W_x$ --- $\mathsf{NP}$ asks you to decide if $W_x$ is non-empty. $\mathsf{BPP}$ is roughly related to whether $W_x$ is large (if "a random string can be a witness"). $\oplus \mathsf{P}$ asks to compute $|W_x|\bmod 2$, and
Mark Schultz-Wu
CC BY-SA 4.0
2020-06-29T20:58:52.103Z
$\#\mathsf{P}$ asks to compute $|W_x|$. One might ask the complexity of computing $|W_x|$ (as this seems to be "at the core" of many of these classes). While computing it exactly is quite hard, there's a technique known as Stockmeyer counting which allows you to compute an approximation of it up to error in $(1+\epsilon)$ within the class $\mathsf{P}^{\Sigma_2}$, i.e. in the third level of the polynomial hierarchy. The third level of the polynomial hierarchy can alternatively be formalized without oracles as follows. Given $x$, decide if $\exists y\forall z \exists w : \varphi(x, y, z, w)$
Mark Schultz-Wu
CC BY-SA 4.0
2020-06-29T21:00:42.420Z
where $\varphi$ is a poly-time computable predicate (and $y,z,w$ are from domains which are not "too large"). Note that $\mathsf{NP}$ can be seen as, given $x$, decide if $\exists y : \varphi(x,y)$, so this is a "generalization of $\mathsf{NP}$" (which is thought to be strict). It can both be phrased concretely (and contains things like Boson Sampling and Stockmeyer Counting), and in terms of oracle machines.
Mark Schultz-Wu
CC BY-SA 4.0
2020-07-27T17:41:08.493Z
@Novicegrammer : It frequently happens in mathematics and theoretical computer science that even if you are primarily interested in studying X, you may need to introduce some other concept Y. Consider nondeterministic Turing machines. These do not directly represent any physically realizable computational device. Yet the complexity class NP provides us with deep insight. Oracles are similar; e.g., Baker-Gill-Solovay theorem tells us that any resolution of the P = NP problem must use non-relativizing techniques. This is a very important insight.
Timothy Chow
CC BY-SA 4.0
2020-07-27T17:43:06.903Z
@Novicegrammer : You can think of the C-T thesis as keeping us "grounded." For theoretical purposes, we can introduce any abstractions that turn out to be convenient or useful. But we shouldn't lose sight of the fact that for practical applications, we eventually have to re-establish contact with the real world. The C-T thesis is an assertion about which of our abstract models actually correspond to things we can carry out in real life.
Timothy Chow
<fl.formal-languages><grammars><church-turing-thesis>
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
Novicegrammer
# Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

(Asked by: username_0 on 2020-06-29)

As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as [Extended Church-Turing Thesis](https://cstheory.stackexchange.com/questions/7528/extended-church-turing-thesis) real-life quantum stuff is even given the time of day, because it's not relevant is it?

I have always thought of the C-T thesis as a statement, specifically a statement in theoretical computer science. A statement that reads, "There exists no computation model capable of recognising languages that a Turing Machine cannot". Even that is a bit messy for me. Is there a formal definition for a computation model? Finite alphabet, finite states, what exactly are we talking about here?

Whether provable or not is another story, but it's a statement that evaluates to some logical value or another. Some people say that the C-T is a statement, some actually say it's not. I have no authority in this, so I'm left as confused as ever.

And if it's *not* a statement, then great! It's not a problem anymore. At least from the mathematical side of things.

I have a couple of what I think are misconceptions. I've taken a look at the `Chomsky Hierarchy` of grammars, and at the very top lie all the so called `Unrestricted Grammars` which have been proven to be equally expressive as Turing Machines, apparently. Now I don't even know the formal definition for *expressivity*, all I have is an intuitive understanding. CFGs are more "expressive" than DFAs and CSGs are more "expressive" than CFGs etc etc, because they can recognise all the languages the prior construction can and more. Is this actually the commonly accepted definition?

Now Unrestricted Grammars specifically, allow *production rules* of the form $\alpha \to \beta$ where $\alpha$ is any non-empty string and $\beta$ is any string. Hence, unrestricted. How on earth could a computational model compete with something that is **literally unrestricted**? It makes me think of the C-T thesis as trivial, "*of course*" it's true.

This left me even more confused: [What would it mean to disprove Church-Turing thesis?](https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis)

The accepted answer to this question starts off with:

> The Church-Turing thesis has been proved for all practical purposes.

Why is practicality suddenly worth anything in theoretical computer science?

Are there like two interpretations or more of the C-T thesis, one for "practical purposes" and one for "mathematics"?

**Tags:** fl.formal-languages, grammars, church-turing-thesis
> **Comments:**
> **username_1**: I think of the Church-Turing thesis (CT) as a hypothesis about the physical universe.  Namely, a _possible computer_ is any device that is constructible in the existing universe (consistent with the laws of physics) for manipulating information. Then CT says that any possible computer can be simulated by a TM.  I guess, historically, the fact that other proposed models of computation can be simulated by a TM gives some empirical evidence for the hypothesis. But from this perspective it is not possible to _prove_ CT (or any other assertion about the physical universe, for that matter).  
> **username_0**: @NealYoung I see, so has CT always been about the physical universe?  
> **username_2**: @Novicegrammer It (kind of) has to be, as Turing Machines equipped with a Halting problem oracle have strictly more computational power than just Turing machines. If this were a "reasonable model of computation", it would constitute a violation of the CT thesis. One way to make it "not reasonable" is to define reasonable as "hypothetically realizable in the universe".  
> **username_0**: I see. Makes me wonder why these "oracles" are a thing and allowed to be considered as computational entities in the first place however...  
> **username_2**: @Novicegrammer The answer to that is "because we can answer interesting questions with them". There are non-trivial results that use oracle machines. For example, given an $\mathsf{NP}$ problem instance $x\stackrel{?}{\in}L$, we can define the "witness set" $W_x$ to be the set of all witnesses to the membership $x\in L$. Many complexity classes can be phrased in terms of $W_x$ --- $\mathsf{NP}$ asks you to decide if $W_x$ is non-empty. $\mathsf{BPP}$ is roughly related to whether $W_x$ is large (if "a random string can be a witness"). $\oplus \mathsf{P}$ asks to compute $|W_x|\bmod 2$, and  
> **username_2**: $\#\mathsf{P}$ asks to compute $|W_x|$. One might ask the complexity of computing $|W_x|$ (as this seems to be "at the core" of many of these classes). While computing it exactly is quite hard, there's a technique known as Stockmeyer counting which allows you to compute an approximation of it up to error in $(1+\epsilon)$ within the class $\mathsf{P}^{\Sigma_2}$, i.e. in the third level of the polynomial hierarchy. The third level of the polynomial hierarchy can alternatively be formalized without oracles as follows. Given $x$, decide if $\exists y\forall z \exists w : \varphi(x, y, z, w)$  
> **username_2**: where $\varphi$ is a poly-time computable predicate (and $y,z,w$ are from domains which are not "too large"). Note that $\mathsf{NP}$ can be seen as, given $x$, decide if $\exists y : \varphi(x,y)$, so this is a "generalization of $\mathsf{NP}$" (which is thought to be strict). It can both be phrased concretely (and contains things like Boson Sampling and Stockmeyer Counting), and in terms of oracle machines.  
> **username_3**: @Novicegrammer : It frequently happens in mathematics and theoretical computer science that even if you are primarily interested in studying X, you may need to introduce some other concept Y. Consider nondeterministic Turing machines. These do not directly represent any physically realizable computational device. Yet the complexity class NP provides us with deep insight. Oracles are similar; e.g., Baker-Gill-Solovay theorem tells us that any resolution of the P = NP problem must use non-relativizing techniques. This is a very important insight.  
> **username_3**: @Novicegrammer : You can think of the C-T thesis as keeping us "grounded." For theoretical purposes, we can introduce any abstractions that turn out to be convenient or useful. But we shouldn't lose sight of the fact that for practical applications, we eventually have to re-establish contact with the real world. The C-T thesis is an assertion about which of our abstract models actually correspond to things we can carry out in real life.  

---

## 3 answers

### Answer by username_2 on 2020-06-29. Score: 7 | Accepted answer

I've written the following to talk about the connections between quantum computation and the (extended) Church-Turing thesis. Your question appears to have several other questions, which I don't address due to space (and time to write down this answer).

---

> A statement that reads, "There exists no "reasonable" computational model capable of recognizing languages that a Turing Machine cannot"

This is essentially what the Church-Turing thesis states. It is *not* the extended Church-Turing thesis, which roughly takes the form:

> All "reasonable" computational models can simulate each other with polynomial overhead

Of course, what "reasonable" means must itself be pinned down. For example, if you let $\mathsf{Halt}$ be an oracle to the halting problem, then the computational model $\mathsf{TM}^{\mathsf{Halt}}$ of Turing Machines equipped with halting oracles can compute strictly more than that than that of simply Turing machines.
So if $\mathsf{TM}^{\mathsf{Halt}}$ is viewed as "reasonable", then the CT thesis is already false.

For this reason, "reasonable" is usually phrased as "hypothetically realizable in the real world". As there is no proposed mechanism to create a universal $\mathsf{TM}^{\mathsf{Halt}}$ machine in the real world, this computational model would not be considered "reasonable".

What does this mean for the extended CT thesis, and quantum computation? The complexity class $\mathsf{BQP}$ is the class of problems solvable (with bounded error) by a quantum computer efficiently. You should view it as a quantum analogue of $\mathsf{P}$ (more properly of $\mathsf{BPP}$, or "two-sided error, randomized $\mathsf{P}$", but still).

**If** quantum computers (which can compute arbitrary problems in $\mathsf{BQP}$) are physically realizable, the extended Church-Turing thesis posits that they can only get a *polynomial* speedup over "traditional" models of computation. If this is the case, the extended Church-Turing thesis still holds, and quantum computing is in a certain sense "more boring".

Preliminary evidence suggests that this is not the case though. There are a variety of problems which are known to have exponential speedups on quantum computers, famously factorization and the discrete logarithm problem via [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm).
While these are large "practical" reasons for investigating quantum computation, they are actually not the theoretically most compelling reason.
Both factorization and discrete log are in $\mathsf{NP}\cap\mathsf{coNP}$, and therefore unlikely to be $\mathsf{NP}$-hard unless the polynomial hierarchy collapses.

This means that "Shor's algorithm leads to an exponential speedup for factoring and discrete log" isn't super interesting from a complexity theory point of view, as it's entirely consistent with current thoughts that both of these problems are actually in $\mathsf{P}$ (or $\mathsf{BPP}$).

There are problems which *are* more interesting to consider though.
In particular, the [Boson sampling](https://en.wikipedia.org/wiki/Boson_sampling#The_complexity_of_the_problem) line of work posits a particular problem which is $\#\mathsf{P}$-hard, but is in $\mathsf{BQP}$.
This means that this particular problem is highly unlikely to be in $\mathsf{P}$, as this would collapse the polynomial hierarchy to the third level, which is thought to be unlikely by complexity theorists.

So the reason that people bring quantum computing up when discussing the (extended) Church-Turing thesis is that, if sufficiently "physically realized", it provides exponential speedups on practically important problems (factoring and discrete logarithm), as well as an exponential speedup on a problem which is "harder than $\mathsf{NP}$-complete". This would constitute a violation of the *extended* Church-Turing thesis.

> **Comments:**
> **username_0**: Speaking of $TM^{Halt}$ as a computational model confuses me. Aren't oracles essentially $O(1)$ "get your answer free card"? Are they also considered as valid, hypothetical computation "devices"?  
> **username_2**: @Novicegrammer Oracle turing machines are usually formalized as "standard" turing machines that have an additional "oracle tape". They can write arbitrary $x\in\{0,1\}*$ to this tape (just like with any other of their tapes). They then have an "oracle query" operation they can call. This is similar to how they have operations like "move tape head left", "move tape head right", etc. You can alternatively view Turing Machines as "uniformly generated circuits", then "oracle queries" are replaced with "oracle gates". This might be a more "concrete" way to view them, depending on your tastes.  
> **username_1**: Just a quick nitpick re: your statement (regarding TM$^{halt}$) that _"For this reason, 'reasonable' is usually phrased as 'hypothetically realizable in the real world'"_.  IMO,  the reason has nothing to do with TM$^{halt}$ per se, or oracles at all for that matter.  IMO the reason is just that _our overall goal is to model computation as it is possible in the physical world, because we are interested in computers that can, in principle, be built and used_.  Note that, e.g., ZFC Set Theory can be used to precisely define all kinds of systems that extend far beyond what we think is computable.  

---

### Answer by username_3 on 2020-07-26. Score: 5

I'll address just the first part of your question.

Neither the Church–Turing Thesis nor the Extended Church–Turing Thesis is a purely mathematical or formal statement. You phrased the C–T Thesis as, "There exists no computation model capable of recognising languages that a Turing Machine cannot." I would recommend not phrasing it this way, because (as you yourself recognize), the term "computation model" sounds like something formal and abstract. But it is *not* the intent of the C–T thesis to assert equality between two purely formal things. Instead, it is a claim that a particular formal model (Turing machines) accurately captures a real-life capability that we have, namely computing. Again, "computing" here is *not* a formally defined thing; it's an informal word for an activity that we physically carry out.

Because the C–T Thesis by its very nature is a statement about the world we physically live in, physics must come into play somehow when we seek to confirm or disconfirm it. It is *not* a purely mathematical conjecture that we can prove or disprove purely mathematically.


---

### Answer by username_4 on 2020-07-26. Score: 1

The Church-Turing thesis is a kind of axiom that links an informal notion of "computation by pen and paper method" to a formal definition of a turing machine model. It has been proven that many different formal machine models can simulate each other and therefore satisfy the same informal notion of computation. They have been proven to be sufficiently similar that it's not usually necessary to distinguish them when discussing computability.

The C-T thesis is sometimes seen in proofs where the author relies on such informal notion of computation and uses the Church-Turing thesis to claim that it's possible to formalize it, usually when such formalization using primitive machine models would be unnecessarily verbose. Often proper proof for claims of proof by C-T thesis is simply to write software that implements the claimed behaviour, using any realistic computer.

It's also possible in certain situations to claim C-T thesis is false. That would mean either that pen-and-paper methods of computation by a human are more powerful than computers - then computers should be extended to add a new primitive operation that cannot be simulated using the existing turing machine model. Or it would mean that current models of computation using computers exceeded the level of sophistication that a human using pen-and-paper computation can perform, where you would rather attempt to improve people's ability to compute.
Since many machine models have been proven to be essentially same in the sense that they can simulate each other computationally, such improvements in computing power are unlikely for the Turing-machine model. There are several attempts to produce such more powerful machines, e.g. quantum computation, but they are usually not realistic enough to be used in practice. But such claims usually have a corresponding claim similar to the Church -Turing thesis, which attempts to formalize such approaches. Of course there are weaker and more limited machine models, which are known to be less powerful, but these can normally be simulated by the more powerful machine models.

Any textbook on computability can explain this in more detail. I can recommend
"Hopcroft&Ullman: Introduction to automata theory, languages and computation".


---

