Halting problem without self-reference

Question

In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a $T$ exists. Then, we consider a case where we restrict $i$ to $M$ itself, and then derive a contradiction by using an instance of a diagonal argument. I am interested how would the proof go if we are given a promise that $i \not = M$? What about promise $i \not = M^\prime$, where $M^\prime$ is functionally equivalent to $M$?

Answer 1

Suppose HALTS is a TM that reads its input as a pair $M$ and $x$, where $M$ is a TM encoding and $x$ is any input to that TM.

Your question is if what would happen if we assumed HALTS solved the halting problem for all inputs $\langle M,x \rangle$ such that $x$ is not an encoding of a TM that is functionally equivalent to $M$.

I claim this implies a contradiction. I came up with this on the spot, so I welcome any and all criticism of my proof. The idea of the proof is that rather than diagonalizing something on itself, we make two mutually recursive TMs that behave differently on some input (thus are not functionally equivalent), but otherwise cause contradictions.

Let $D_1$ and $D_2$ be two mutually recursive TMs (which is to say we can simulate, print, etc, the description of $D_2$ inside the program of $D_1$ and vice versa). Note that we can make mutually recursive TMs from the recursion theorem.

Define $D_1$ and $D_2$ as follows: on input $x$, if $|x| < 10$ (10 chosen arbitrarily), then $D_1$ accepts and $D_2$ loops. (Thus, they are not functionally equivalent).

Given input $x$ with $|x| \ge 10$, define $D_1$ to simulate HALTS on $\langle D_2, x \rangle$ and halt if $D_2$ halts or loop if $D_2$ loops.

Given input $x$ with $|x| \ge 10$, define $D_2$ to simulate HALTS on $\langle D_1, x \rangle$ and loop if $D_1$ halts or halt if $D_1$ loops.

Then note that for any $x$ with $|x| \ge 10$, $D_1$(x) either halts or loops. If $D_1$ halts on input x, then we know HALTS($D_2$, x) determined that $D_2$ halts on input x. However, $D_2$ halting on input x implies that HALTS($D_1$, x) loops.

If $D_1$ on input $x$ loops, the contradiction follows similarly.

This is a contradiction unless $x$ is an encoding for a turing machine functionally equivalent to $D_1$ or $D_2$, in which case HALTS has undefined behavior. However, $x$ was chosen at arbitrary from all strings of size greater than $10$. Thus, it remains to show there exists a turing machine with an encoding of size greater than 10 that behaves differently than $D_1$ and $D_2$. We can construct such a machine trivially. QED.

Thoughts?

Answer 2

You're still not out of the woods. You run into the same problem, only now you give it a different TM, $M'$ as input, where you've chosen $M'$ to be functionally equivalent to $M$ (say you add a new rule to $M$ so that $M'$s opening moves are one step right, one step left and otherwise you make no changes). You'll still run into a contradiction. You might try eliminating all the TMs that are equivalent to $M$, but that's an undecidable set.

---

Update. Fix an encoding scheme where $\langle\,M\,\rangle$ denotes the description under that scheme of a TM $M$ and suppose you had a TM, $H$ where

• $H(\langle\,M\,\rangle, x)$ is undefined when $x$ is the encoding of a TM which computes the same partial function as $H$ (i.e., $x$ and $H$ are functionally equivalent).
• For all other inputs, $H(\langle\,M\,\rangle, x)$ returns true if and only if $M(x)$ halts.

Now the usual diagonalization construction still results in a contradiction. Define a TM $Q$ by

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

Clearly $Q$ and $H$ are functionally inequivalent, so we can let $x=\langle\,Q\,\rangle$ and find that $Q(\langle\,Q\,\rangle)$ halts if and only if it doesn't halt, so there can be no such TM $H$.