<p><strong>P1</strong> Perhaps you can somewhat avoid self reference in this way.</p>
<p>Let <span class="math-container">$S_k$</span> be the total number of steps performed by the <em>halting</em> Turing machines of size <span class="math-container">$\leq k$</span> in their computation.</p>
<p>Suppose the Halting problem is solvable, then <span class="math-container">$S_k$</span> is computable and exists a TM <span class="math-container">$M_S$</span> that on input <span class="math-container">$k$</span> enumerates the Turing machines of size <span class="math-container">$\leq k$</span>, for each one of them check if it halts, if it halts simulate it step by step and keep track of the total sum of steps.</p>
<p>You can build a &quot;small&quot; <span class="math-container">$M$</span> that:</p>
<ul>
<li>embeds a number <span class="math-container">$n$</span> in binary format</li>
<li>calculatate <span class="math-container">$2^n$</span></li>
<li>apply the <span class="math-container">$M_S$</span> &quot;function&quot; on <span class="math-container">$2^n$</span> and calculate <span class="math-container">$S_{2^n}$</span> using the method above</li>
</ul>
<p>For large enough <span class="math-container">$n$</span> we have <span class="math-container">$|M| &lt; 2^n$</span>, but this is a contradiction because there is a Turing machine of size <span class="math-container">$&lt;2^n$</span> that halts after a number of steps greater than <span class="math-container">$S_{2^n}$</span>.</p>
<p><strong>P2</strong> Another somewhat obscure proof could be:</p>
<p>You can build a TM <span class="math-container">$M$</span> that checks if there is a proof of <span class="math-container">$A \land \lnot A$</span> in Peano Arithmetic (enumerating the valid proofs), and if it founds one then it halts.
If the Halting problem is solvable, you could be able to prove the consistency of PA within PA itself, which is a contradiction of the second Godel's incompleteness theorem.</p>

CC BY-SA 4.0
2023-04-01T18:30:27.390Z
2023-04-01T18:38:06.850Z
2023-04-01T18:38:06.850Z
Marzio De Biasi
<p>Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever?</p>
<p>All the <a href="https://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-dep?noredirect=1&amp;lq=1">duplicate questions</a> I have come across end up either <a href="https://cstheory.stackexchange.com/questions/3837/alternative-turing-machine-proofs">in arguments</a>, or not providing answers that satisfy the conditions put forth. As a result, the few answers that do satisfy the conditions above are scattered across different questions.</p>
<p>To be clear, I'm not bothered with the standard proof (or its variants). I'm only looking for those that match the above conditions.</p>

CC BY-SA 4.0
2023-03-31T16:15:32.070Z
I don't see how one can avoid "proof by contradiction": you want to show that something does not exists (namely an algorithm for the Halting problem) and as far as I know the only way to do that is to show that the existence of such an algorithm gives you a contradiction.
Reijo Jaakkola
CC BY-SA 4.0
2023-03-31T17:32:24.707Z
@ReijoJaakkola Even then, it does not rule out the possibility of such a proof existing. Maybe such an algorithm must have properties that cannot be held simultaneously by any algorithm. I do understand the issue however, and I have edited the question accordingly.
Alan Whitteaker
CC BY-SA 4.0
2023-03-31T19:49:44.407Z
Possibly related: [Chaitin's incompleteness theorem](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin%27s_incompleteness_theorem)
Neal Young
CC BY-SA 4.0
2023-04-01T07:38:35.477Z
@ReijoJaakkola a bit of nitpicking: what you are referring to is not a "proof by contradiction", it is just a "proof of negation": in order to prove $\lnot A$, you assume $A$ and derive a contradiction.  A "proof by contradiction", instead, assumes $\lnot A$, derives a contradiction, and concludes $A$ (rather than $\lnot\lnot A$, as "proof of negation" would allow you to do).  Many confuse the two, the difference is subtle but it's fundamental for those who are interested in constructive logic.  Of course all this has no bearing on the OP's question.
Damiano Mazza
CC BY-SA 4.0
2023-04-01T08:21:41.200Z
@DamianoMazza Fair point, although I guess this distinction is useful only in the context of logics such as the constructive logic. E.g., to prove $A=$ "there is no algorithm for the Halting problem" using "proof by a contradiction", you derivate a contradiction from the assumption $\neg A$ which is in classical logic equivalent to "there exists an algorithm for the Halting problem". Of course, if OP wants a constructive proof, then this distinction applies and your point is a valid one.
Reijo Jaakkola
CC BY-SA 4.0
2023-04-04T18:48:37.287Z
@ReijoJaakkola sorry, I see this only now.  You are still *not* actually using proof by contradiction.  If $B$ is "there is an algorithm for the Halting problem", your $A$ is $\lnot B$, so assuming $\lnot A$ means assuming $\lnot\lnot B$.  If this implies a contradiction, proof of negation gives you $\lnot\lnot\lnot B$, which is constructively equivalent to $\lnot B$ (no classical logic needed).  So, either $B$ implies a contradiction, and you get $\lnot B$ constructively, or $\lnot\lnot B$ implies a contradiction, and you still get $\lnot B$ constructively.
Damiano Mazza
CC BY-SA 4.0
2023-04-04T18:52:13.210Z
The bottom line is: no matter how you turn it around, the undecidability of the Halting problem is a constructive result (it holds in intuitionistic logic).  I honestly would have no idea how a "proof by contradiction" of the undecidability of the Halting problem would go...  Again, this is irrelevant for the (current version of the) OP's question: whether there is a proof not using self-reference, diagonalization, etc. is a completely different matter.
Damiano Mazza
<turing-machines><proofs><decidability><halting-problem><undecidability>
Halting problem proofs that do not utilise self-reference or diagonalization
Alan Whitteaker
# Halting problem proofs that do not utilise self-reference or diagonalization

(Asked by: username_0 on 2023-03-31)

Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever?

All the [duplicate questions](https://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-dep?noredirect=1&lq=1) I have come across end up either [in arguments](https://cstheory.stackexchange.com/questions/3837/alternative-turing-machine-proofs), or not providing answers that satisfy the conditions put forth. As a result, the few answers that do satisfy the conditions above are scattered across different questions.

To be clear, I'm not bothered with the standard proof (or its variants). I'm only looking for those that match the above conditions.

**Tags:** turing-machines, proofs, decidability, halting-problem, undecidability

> **Comments:**
> **username_1**: I don't see how one can avoid "proof by contradiction": you want to show that something does not exists (namely an algorithm for the Halting problem) and as far as I know the only way to do that is to show that the existence of such an algorithm gives you a contradiction.  
> **username_0**: @ReijoJaakkola Even then, it does not rule out the possibility of such a proof existing. Maybe such an algorithm must have properties that cannot be held simultaneously by any algorithm. I do understand the issue however, and I have edited the question accordingly.  
> **username_2**: Possibly related: [Chaitin's incompleteness theorem](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin%27s_incompleteness_theorem)  
> **username_3**: @ReijoJaakkola a bit of nitpicking: what you are referring to is not a "proof by contradiction", it is just a "proof of negation": in order to prove $\lnot A$, you assume $A$ and derive a contradiction.  A "proof by contradiction", instead, assumes $\lnot A$, derives a contradiction, and concludes $A$ (rather than $\lnot\lnot A$, as "proof of negation" would allow you to do).  Many confuse the two, the difference is subtle but it's fundamental for those who are interested in constructive logic.  Of course all this has no bearing on the OP's question.  
> **username_1**: @DamianoMazza Fair point, although I guess this distinction is useful only in the context of logics such as the constructive logic. E.g., to prove $A=$ "there is no algorithm for the Halting problem" using "proof by a contradiction", you derivate a contradiction from the assumption $\neg A$ which is in classical logic equivalent to "there exists an algorithm for the Halting problem". Of course, if OP wants a constructive proof, then this distinction applies and your point is a valid one.  
> **username_3**: @ReijoJaakkola sorry, I see this only now.  You are still *not* actually using proof by contradiction.  If $B$ is "there is an algorithm for the Halting problem", your $A$ is $\lnot B$, so assuming $\lnot A$ means assuming $\lnot\lnot B$.  If this implies a contradiction, proof of negation gives you $\lnot\lnot\lnot B$, which is constructively equivalent to $\lnot B$ (no classical logic needed).  So, either $B$ implies a contradiction, and you get $\lnot B$ constructively, or $\lnot\lnot B$ implies a contradiction, and you still get $\lnot B$ constructively.  
> **username_3**: The bottom line is: no matter how you turn it around, the undecidability of the Halting problem is a constructive result (it holds in intuitionistic logic).  I honestly would have no idea how a "proof by contradiction" of the undecidability of the Halting problem would go...  Again, this is irrelevant for the (current version of the) OP's question: whether there is a proof not using self-reference, diagonalization, etc. is a completely different matter.  

---

## 1 answers

### Answer by username_4 on 2023-04-01. Score: 3

**P1** Perhaps you can somewhat avoid self reference in this way.

Let $S\_k$ be the total number of steps performed by the *halting* Turing machines of size $\leq k$ in their computation.

Suppose the Halting problem is solvable, then $S\_k$ is computable and exists a TM $M\_S$ that on input $k$ enumerates the Turing machines of size $\leq k$, for each one of them check if it halts, if it halts simulate it step by step and keep track of the total sum of steps.

You can build a "small" $M$ that:

* embeds a number $n$ in binary format
* calculatate $2^n$
* apply the $M\_S$ "function" on $2^n$ and calculate $S\_{2^n}$ using the method above

For large enough $n$ we have $|M| < 2^n$, but this is a contradiction because there is a Turing machine of size $<2^n$ that halts after a number of steps greater than $S\_{2^n}$.

**P2** Another somewhat obscure proof could be:

You can build a TM $M$ that checks if there is a proof of $A \land \lnot A$ in Peano Arithmetic (enumerating the valid proofs), and if it founds one then it halts.
If the Halting problem is solvable, you could be able to prove the consistency of PA within PA itself, which is a contradiction of the second Godel's incompleteness theorem.


---

