I want to make a modification to the halting problem. The output now has two possibilities:
- This program halts and it does not have the crossing structure (defined below);
- This program does not halt or it has the crossing structure.
A crossing structure simply means the program 1) simulates me and 2) contradicts my verdict. Note that the crossing structure is static property about the code. Note also how the crossing structure interacts with whether the program halts: If it's very clean, then it goes to the first category. If it's ugly, then it goes to the second.
This means that Turing has pointed out a third category of programs, or rather a distinction between "This program halts." and "I can decide that this program halts, correctly or provably." Because being a program, it can only murmur the second kind of sentences. Therefore I'm finding a way around this undecidability phenomenon. I think its main course is not because this problem is hard, but rather the program has limited expressiveness. It's a program, not an independent observer. We must take into account this fact. To it, there are three possibilities, instead of two. And it must have a way to express this fact. If you assume it can just decide truth, then you are assuming it's independent, which is clearly not the case. I guess here is Turing's mistake and here is the conclusion of the proof by contradiction. The existence of a Turing machine solving the halting problem is not surprising, but, being a program, it needs a little expressiveness to show that in, its world, there are three possibilities instead of two!
Now let me show that Rice's theorem does not work in this case. That is, I can define a program that separate all programs into these two sets. Given a program $p$ and an input $i$, I will make the program $t$ that 1) simulates $p$ on $i$ and 2) halts. Then
- If $p$ halts on $i$ and $p$ does not have the crossing structure, then this pair belongs to the first category.
- If $p$ has the crossing structure, the this pair belongs to the second category.
- If $p$ does not halt on $i$, then this pair belongs to the second category.
Let me try to follow the proof of the undecidability of the halting problem. So we make a new program $P$ based on my program $M$. $P$ will have the crossing structure.
Then no problem, $P$ will belong to the second category. Even if it rebels and runs forever, I'm still right in saying that it belongs to the second category. First, I have the code of $P$. So I know whether it has the crossing structure or it runs forever. If it's very clean, then it goes to the first category. Otherwise it belongs to the second category.
Yous see, I'm looking at $P$. Either it has a crossing structure or it does not. I'm not deciding this. I'm deciding, instead, whether it's pure, meaning it halts and does not have the crossing structure, or contaminated. OK, it has two cases. If it has a crossing structure, it goes to the second category. If it does not, it goes to a category according to whether it halts or not. This case distinction is just for analysis, not what the program does.
You see this definition makes the two cases, against Rice's theorem and against the undecidability property, almost automatic. Therefore I suspect it's the right definition.
The question is whether this "halting problem" can be solved.
Suppose I'm such a program, i.e. such a program exists.
Then there is 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.