9
$\begingroup$

This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help.

Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself? Basically:

Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

This seemingly resolves the contradiction. When we call the paradoxical Halts'(Halts'), we can't expect consistent behavior, but all other calls to Halts (and Halts') are legitimate and solvable.

I understand that this is highly unintuitive. If some pattern in the bits could reveal the behavior of all possible programs, why would it suddenly fall apart when the TM and input match? But can we mathematically eliminate this as a possibility?

And this reduced halting problem would not be uninteresting at all. Even if there were some meaningful program that took its own code as input it could trivially be rewritten to work on slightly different input. Of course this suggestion makes it even less understandable why a halting solution could exist with this one caveat but again, can we really mathematically eliminate this possibility?

Thanks for any help.

$\endgroup$
  • 7
    $\begingroup$ Decidability is not affected by finite changes. ​ ​ $\endgroup$ – user12859 Apr 12 '16 at 6:08
  • $\begingroup$ there are an infinite # of equivalent TMs, and there is no (decidable) way to detect equivalent TMs (ie its essentially the same as the halting problem itself). however there are some complex "loopholes"; try Computer Science Chat for further analysis of the halting problem related to automated thm proving etc... might try to cook this into an answer... $\endgroup$ – vzn Apr 12 '16 at 15:10
  • $\begingroup$ Touched up my question to be a little clearer, sorry if I mislead anyone. $\endgroup$ – CS101 Apr 12 '16 at 17:10
  • $\begingroup$ The answer is no, as in this answer cstheory.stackexchange.com/questions/2853/… $\endgroup$ – M. Alaggan Apr 18 '16 at 9:21
4
$\begingroup$

But we can easily get round your restriction. Suppose a program $G$ that reverses the bits of the input and calls your $H'$ on the result, then define $!H$ with all bits reversed (i.e. 0 for 1s, 1s for 0s). Then we can call your $H'$ with $G(!H)$ and we're back to the original problem.

$\endgroup$
  • $\begingroup$ Thank you. After reading @David Richerby's answer I started thinking that this is the answer. If we can construct a functionally equivalent Q' for all programs Q, then we can once again decide haltability for all problems, not just the ones off the diagonal. I see this is what you're saying. $\endgroup$ – CS101 Apr 12 '16 at 17:07
12
$\begingroup$

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ uses $H$ to determine if $M(\langle M\rangle)$ halts and, if so, $Q$ loops; otherwise, $Q$ halts. Now, $Q(\langle Q\rangle)$ halts if, and only if, it doesn't halt.

Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself?

No. If you change the definition of the halting problem in this way, the proof still works. We don't care what happens when $H$ receives $\langle H\rangle$ as input because the contradiction comes after we give input $\langle Q\rangle, \langle Q\rangle$ to $H$.

Second, if you modified $H$ to detect that input, we could get the same contradiction by using any other machine $Q'$ that is equivalent to $Q$ in the sense that, for any input $w$, $Q'(w)$ halts if, and only if, $Q(w)$ halts. There are infinitely many of these and $H$ can't detect all of them because it's undecidable whether two Turing machines are equivalent.

$\endgroup$
  • 3
    $\begingroup$ The last paragraph alone may be enough to answer the question: you can not hardcode away all encodings of equivalent machines no matter which finite adaption (based on semantics) you want to perform. (That is not to say that the rest of your post isn't worthwhile reading!) $\endgroup$ – Raphael Apr 12 '16 at 9:29
  • $\begingroup$ Thank you for the answer. Isn't the undecidability of whether or not programs are functionally equivalent itself derived from the undecidability of the halting problem? Why would this not be circular reasoning? $\endgroup$ – CS101 Apr 12 '16 at 17:01
  • 1
    $\begingroup$ @CS101: the undecidability of $\mathrm{HALT}$ is a theorem once and for all, we aren't "cheating" when we use it to show that it is impossible to solve another problem $\mathrm{HALT'}$ which tries to get around the restriction. As a side note, we do know pragmatically how to prove termination or non-termination of many practical programs (just not all programs). However, proving equivalence of programs turns out to be significantly harder in practice (even though they are both undecidable). $\endgroup$ – cody Apr 12 '16 at 18:24
  • $\begingroup$ Confused myself, forgot the full halting problem is still the same per my conjecture. Thanks. $\endgroup$ – CS101 Apr 12 '16 at 18:45

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.