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.