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.

  • $\begingroup$ No no no. If you can do this, then you can separate the $P$s from the non-$P$s. This will imply you can solve the original halting problem. Because given a pair $(p,i)$, we can make a Turing machine $t$ that first simulates $p$ on $i$ and then does what $P$ does. If $p$ halts on $i$, $t$ belongs to the $P$s. If $p$ does not halt on $i$, $t$ belongs to the non-$P$s. So deciding whether $t$ belongs to the $P$s is equivalent to deciding whether $p$ halts on $i$. Defeat. $\endgroup$ – Zirui Wang Nov 5 '11 at 20:40
  • 2
    $\begingroup$ I think this is more suitable for Math.SE. $\endgroup$ – Kaveh Nov 5 '11 at 20:48
  • $\begingroup$ What if I write my answer in a CAPTCHA? I mean something humans can do but computers can't recognize. $\endgroup$ – Zirui Wang Nov 5 '11 at 20:51
  • 3
    $\begingroup$ cstheory.stackexchange.com is for research-level questions in theoretical computer science. Not all questions in theoretical computer science are suitable on cstheory.stackexchange.com. $\endgroup$ – Tsuyoshi Ito Nov 5 '11 at 21:20
  • 5
    $\begingroup$ @Zirui Wang, please don't post questions which you know are not research level, they are off-topic for cstheory. $\endgroup$ – Kaveh Nov 6 '11 at 11:00

Let's call your answers "yes" (the given program halts), "no" (the given program does not halt) and "maybe". If I understand you correctly, you are redefining the Haltin problem as follows.

Zirui's Problem: Is there a machine $M$ such that, on a given input $k$ representing a machine $K$, $M$ halts and:

  1. if $K$ tries to trick $M$ then:
    • if $K$ halts then $M$ must answer "yes" or "maybe"
    • if $K$ does not halt them $M$ must answer "no" or "maybe"
  2. if $K$ does not try to trick $M$ then:
    • if $K$ halts then $M$ must answer "yes"
    • if $K$ does not halt then $M$ must answer "no"

For the sake of the argument, let us suppose we can actually figure out that it means for "$K$ to trick $M$".

You considered in your question the case when $M$ is supposed to fight against just one machine $P$ that tries to trick it. However, there will be infinitely many other machines $P_1, P_2, \ldots$ that try to trick $M$. These are just variations on $P$, with modifications of source code, using slightly different algorithms, etc.

Let us make one further reasonable assumption. Without loss of generality, think of machines as computing partial functions from $\mathbb{N}$ to $\mathbb{N}$ (just encode inputs and outputs as numbers in a reasonable way). Our extra assumption is this: if $P$ and $P'$ compute the same function (but maybe using different algorithms), and $P$ tries to trick $M$, then also $P'$ tries to trick $M$. In other words, "tries to trick" is a property of machines which does not depend on how they work but on what they do.

By Rice's theorem $M$ cannot correctly recognize all the machines that try to trick it. Therefore, either it gets tricked by some machine, or it answers "maybe" for some innocent machine that is not trying to trick it.

  • 1
    $\begingroup$ This answer is not uninteresting, but I think that the problem with the question is more of defining what it means for a machine to trick another machine than actually deciding it. $\endgroup$ – Tsuyoshi Ito Nov 5 '11 at 20:53
  • $\begingroup$ I made a change to my proposal, to accommodate Rice's theorem. Namely, two outputs: "halt and not paradoxical" and "not halt or paradoxical". This makes sure that Rice's theorem does not apply. So I think Rice's theorem is also not essential, i.e. it can be avoided. I convinced myself of this point. But is there a bug? I'd like to hear it urgently. $\endgroup$ – Zirui Wang Nov 5 '11 at 22:46

Let me try to summarize what you're saying.

A. The program halts; or
B. The program may or may not halt.
C. The program never halts (this will come later).

The halting problem is sorting a program definitively into A or C.

Given a program p and an input i, I will make the program t that 1) simulates p on i and 2) halts.

So you create a program t that simulates p(i) for s seconds and then halts, mapping t:p(i)->(A|B)

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:

So M is t(p(i)); M:p(i)->(A|B) = t:p(i)->(A|B). So we might as well keep calling it t.
And P is P:t(p(i))->(A|C) = P:(A|B)->(A|C)

  • If I say halt, then P will not halt;
  • If I say not halt or no answer, then P will halt.

So if [1] t(p(i)) = A (p(i) halts), then P does not halt (C).
Or if [2] t(p(i)) = B (p(i) did not halt in the time allotted), then P halts (A).

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.

I'm not clear what you're trying to say here, especially the "rebels and runs forever" part.
In [1], yes, P does not halt, so it is clearly in group C.
In [2], t halts, so M halts, so P halts. So P is in group A.

So, are you trying to say that you can tell whether P halts? Sure, that's not hard, because you're defining it to halt or not based on the output of a machine known to halt. You might as well say you solved the halting problem for t, since you defined it to always halt.

You still didn't address the general halting problem, which is whether p (lowercase, not P) halts.

  • $\begingroup$ I am addressing the general halting problem, but I noticed a difficulty of the program. Or rather a difference between a program decider and a human decider. The program can have nemesis, so it must be able to report those. If it can only speak "yes" or "no", then it's like mute person who knows a lot but can't express what he finds. Note that this is a program and it can have nemesis. I think you accept this fact. Then what to do with nemesis? My approach is put these clever opponents into a separate category. Yet, to avoid Rice's theorem, I merged these with those do not halt. Any problem? $\endgroup$ – Zirui Wang Nov 6 '11 at 8:23

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