Is it possible that the halting problem is solvable for all input except the machine's code?

Problem Detail: 

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.

Asked By : CS101

Answered By : Jack Aidley

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

Best Answer from StackOverflow

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