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

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ Decidability is not affected by finite changes. ​ ​ $\endgroup$
    – user12859
    Apr 12, 2016 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, 2016 at 15:10
  • $\begingroup$ Touched up my question to be a little clearer, sorry if I mislead anyone. $\endgroup$
    – CS101
    Apr 12, 2016 at 17:10
  • $\begingroup$ The answer is no, as in this answer cstheory.stackexchange.com/questions/2853/… $\endgroup$
    – Mohammad Alaggan
    Apr 18, 2016 at 9:21

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2016 at 17:07
14
$\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.

Improve this answer
$\endgroup$
4
  • 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, 2016 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, 2016 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, 2016 at 18:24
  • $\begingroup$ Confused myself, forgot the full halting problem is still the same per my conjecture. Thanks. $\endgroup$
    – CS101
    Apr 12, 2016 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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