Attempted proof of undecidability of halting problem

62 Views Asked by At

I've heard before that the proof of the halting problem is a straightforward application of a diagonalization argument. However, I haven't actually tried to carry it out before. I think the argument works, but it ended up being really straightforward. I'm wondering whether I missed something major.


A run of a Turing machine is the result of running it with particular input and output.

I nonstandardly define a pseudo-oracle as a Turing machine that can answer some kind of semantic predicate on its arguments, a halting pseudo-oracle can tell whether a run constructed in some way from its arguments halts or not.

Let's consider Turing machines with two input tapes and one output tape, henceforth $T$. I will constrain the input tapes to include a finite prefix of bits that can be either $0$ or $1$, and the rest must be $0$. In particular, let the natural number $n$ correspond to the binary string associated with the little-endian representation of $n$ in binary, with infinitely many zeroes extending to the right. Turing machines with other numbers of input and output tapes can be "compiled into" members of $T$, but for the moment I want to consider the 2-1 variety.

I will assume we have a bijection from $T$ to $\mathbb{N}$ without constructing it explicitly. Call the nth turning machine $T_n$.

If $n$ is a natural number, let $n^*$ be a function of type $\mathbb{N} \times \mathbb{N} \to \mathbb{N} \cup \{\infty\} $ so that $n^*(a, b) = \infty$ if the Turing machine $T_n$ does not halt when given $a$ on its first tape and $b$ on its second tape. If $c$ is a natural number, then $n^*(a, b) = c$ means that when given $a$ and $b$ as inputs, the Turing machine $T_n$ will halt after finitely many steps with $c$ as the value of the output tape. If a run of a Turing machine halts, the machine necessarily will have written finitely many values on its output type.

A solution to the halting problem means that we have a Turing machine that can determine in finite time whether an arbitrary turing machine halts with particular input.

In particular, a solution to the halting problem implies the existence of $t$, a limited halting pseudo-oracle that determines whether its first argument halts when given its second argument twice.

$$ t^*(x, y) = 0 \;\; \text{iff} \;\; x^*(y, y) \in \mathbb{N} $$ $$ t^*(x, y) = 1 \;\; \text{iff} \;\; x^*(y, y) = \infty $$

We then define a turing machine $T_s$ as follows. $s$ consumes the output of $t$, and goes into an infinite loop if $t$ returns $0$. A Turing machine can inspect the output of another Turing machine if the latter halts, and a Turing machine can decide to explicitly enter an infinite loop, so $T_s$ is a Turing machine.

$$ s^*(x, y) = \infty \;\; \text{iff} \;\; t^*(x, y) = 0 $$ $$ s^*(x, y) = 1 \;\; \text{iff} \;\; t^*(x, y) = 1 $$

We now consider the value of $s^*(s, s)$.

$$ \;\;\text{If}\;\; s^*(s, s) = \infty \;\; \text{then} \;\; t^*(s, s) = 0 \;\; \text{then} \;\; s^*(s, s) \in \mathbb{N} $$

Which is a contradiction.

$$ \;\;\text{If}\;\; s^*(s, s) = 1 \;\; \text{then} \;\; t^*(s, s) = 1 \;\; \text{then} \;\; s^*(s, s) = \infty $$

Which is a contradiction.

Therefore $s^*(s, s)$ isn't $\infty$ and isn't $1$, which contradicts the definition of $s$.

Therefore, the limited halting pseudo-oracle Turing machine $T_t$ that we hypothesized the existence of doesn't exist.

Therefore a full halting pseudo-oracle Turing machine doesn't exist.