I think the halting problem is not a result regarding computability, but rather expressiveness or restrictiveness. It's like asking a computer to prove $0=1$ or color a planar graph using only $3$ colors. To accommodate this lack of expressiveness, I propose to change the yes-no output options to these two:
- This program halts and it does not have a crossing structure.
- This program does not halt or it has a crossing structure.
The key here is that I merged the case "does not halt" and the case "has a crossing structure". And this will stop Rice's theorem from being able to be applied here.
Now, what is a crossing structure? It simply means that the input machine simulates the decider and does the opposite of its verdict.
So much for the definitions. My question is:
Is the halting problem solvable with these two output meanings?
My suspicion is that it's still not solvable, but yet it's consistent with all my test cases.
This is actually a paradox. The question is:
Is there a program with a crossing structure?
First suppose there is. Then this program will simulate me. Suppose I say you don't halt or you have a crossing structure. Then you must, in order to contradict me, halt and at the same time don't possess a crossing structure. Contradiction.
Next suppose there isn't any. Then "halt and don't possess a crossing structure" is equivalent to "halt" and "don't halt or possess a crossing structure" is equivalent to "don't halt". Then it's easy to contradict me, that is, there is a program possessing the crossing structure. Again, contradiction.