9
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Hint: even if $M$ is not required to correctly answer questions about itself or even about $M'$'s equivalent to it, we can still feed it an equivalent $M'$ and see what it does. Because it is not computable whether $M'$ is equivalent to $M$, $M$ will not be able to tell it got something equivalent to itself. $\endgroup$ – Andrej Bauer Aug 7 '14 at 12:25
  • $\begingroup$ @AndrejBauer Was this just a hint you gave me and I should solve my actual problem using this hint? I am a bit confused, since you relax the problem by saying "not requiring", where in my setting I have a promise that $M$ will not be fed with an equivalent $M^\prime$. Basically, I would like to see is any sort of "self-reference" the thing that makes problems undecidable. I was thought that this is the case when talking about logic and incompleteness. $\endgroup$ – bellpeace Aug 7 '14 at 17:31
  • $\begingroup$ You can break the promise and feed $M$ whatever you like. It can't tell you broke the promise, anyway. If you think that's cheating, then I'll feed $M$ things which aren't equivalent to $M$ because they are like $M$ but with all the inputs shifted by $1$, or some such. $\endgroup$ – Andrej Bauer Aug 7 '14 at 20:27
  • $\begingroup$ Actually, your questions isn't well formulated. You should outline the actual proof you have in mind, and then specify what precisely you want to avoid. I don't think you mean $i \neq M$, but something else. $\endgroup$ – Andrej Bauer Aug 7 '14 at 20:33
7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why do you need to make sure $D_1$ and $D_2$ are not functionally equivalent? $\endgroup$ – bellpeace Aug 8 '14 at 3:46
  • $\begingroup$ I think you're correct that this is not necessary. My original intent was to diagonalize on HALTs($\langle D_1, D_2 \rangle$) $\endgroup$ – Kurt Mueller Aug 11 '14 at 13:14
  • $\begingroup$ Without that, the proof is more elegant, but it anyway looks good to me and is exactly what I needed. $\endgroup$ – bellpeace Aug 11 '14 at 17:36
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ And suppose that I have a promise that $i$ is not a TM functionally equivalent to $M$? Maybe I can extend my question in the OP? $\endgroup$ – bellpeace Aug 7 '14 at 1:43
  • 1
    $\begingroup$ Suppose that you are given such a promise; I know it is not computable. I have updated the OP. $\endgroup$ – bellpeace Aug 7 '14 at 2:10
  • $\begingroup$ @bellpeace : $\:$ How do you even define that? $\;\;\;\;$ $\endgroup$ – user12859 Aug 7 '14 at 4:12
  • $\begingroup$ Input: a pair of integers $(M, i)$ such that $i$ does not represent a TM functionally equivalent to TM represented by $M$. Output: $1$ if $M$ halts on $i$, $0$ otherwise. Is this problem decidable? $\endgroup$ – bellpeace Aug 7 '14 at 4:28
  • 1
    $\begingroup$ @RickyDemer Yes, two TMs are considered functionally equivalent if they compute the same partial function. Note that, as Andrey pointed out, that although determining whether $M$ and $M^\prime$ are equivalent is undecidable, we can still consider the problem where we are given a promise that two input TMS are not equivalent, just as I have exemplified above. $\endgroup$ – bellpeace Aug 7 '14 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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