4
$\begingroup$

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 I have come across end up either in arguments, 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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Reijo Jaakkola
    Commented Mar 31, 2023 at 16:15
  • $\begingroup$ @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. $\endgroup$
    – Alan Whitteaker
    Commented Mar 31, 2023 at 17:32
  • $\begingroup$ Possibly related: Chaitin's incompleteness theorem $\endgroup$
    – Neal Young
    Commented Mar 31, 2023 at 19:49
  • 5
    $\begingroup$ @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. $\endgroup$
    – Damiano Mazza
    Commented Apr 1, 2023 at 7:38
  • $\begingroup$ @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. $\endgroup$
    – Reijo Jaakkola
    Commented Apr 1, 2023 at 8:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.