[Solved]: Halting problem without self-reference

Problem Detail: 

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$?

Asked By : bellpeace

Answered By : Kurt Mueller

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28963