<p>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.</p>

<blockquote>
  <p><strong>Zirui's Problem</strong>: Is there a machine $M$ such that, on a given input $k$ representing a machine $K$, $M$ halts and:</p>
  
  <ol>
  <li>if $K$ tries to trick $M$ then:
  <ul>
  <li>if $K$ halts then $M$ must answer "yes" or "maybe"</li>
  <li>if $K$ does not halt them $M$ must answer "no" or "maybe"</li>
  </ul></li>
  <li>if $K$ does not try to trick $M$ then:
  <ul>
  <li>if $K$ halts then $M$ must answer "yes"</li>
  <li>if $K$ does not halt then $M$ must answer "no"</li>
  </ul></li>
  </ol>
</blockquote>

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

<p>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.</p>

<p>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&#39;$ compute the same function (but maybe using different algorithms), and $P$ tries to trick $M$, then also $P&#39;$ tries to trick $M$. In other words, "tries to trick" is a property of machines which does not depend on <em>how</em> they work but on <em>what</em> they do.</p>

<p>By <a href="http://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow">Rice's theorem</a> $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.</p>

CC BY-SA 3.0
2011-11-05T20:53:25.223Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-05T22:46:42.577Z
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.
Zirui Wang
CC BY-SA 3.0
2011-11-05T20:32:46.690Z
2011-11-05T20:32:46.690Z
Andrej Bauer
<p>Let me try to summarize what you're saying.</p>

<p>A. The program halts; or<br>
 B. The program may or may not halt.<br>
 C. The program never halts (this will come later).</p>

<p>The halting problem is sorting a program definitively into A or C.</p>

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

<p>So you create a program <em>t</em> that simulates p(i) for s seconds and then halts, mapping <code>t:p(i)-&gt;(A|B)</code></p>

<blockquote>
  <p>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>
</blockquote>

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

<blockquote>
  <ul>
  <li>If I say halt, then P will not halt;</li>
  <li>If I say not halt or no answer, then P will halt.</li>
  </ul>
</blockquote>

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

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>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.</p>

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

CC BY-SA 3.0
2011-11-06T08:23:41.863Z
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?
Zirui Wang
CC BY-SA 3.0
2011-11-06T01:12:04.487Z
2011-11-06T01:12:04.487Z
Kevin
<p>I want to make a modification to the halting problem. The output now has two possibilities:</p>

<ul>
<li>This program halts and it does not have <em>the crossing structure</em> (defined below);</li>
<li>This program does not halt or it has the crossing structure.</li>
</ul>

<p>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.</p>

<p>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!</p>

<p>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</p>

<ul>
<li>If $p$ halts on $i$ and $p$ does not have the crossing structure, then this pair belongs to the first category.</li>
<li>If $p$ has the crossing structure, the this pair belongs to the second category.</li>
<li>If $p$ does not halt on $i$, then this pair belongs to the second category.</li>
</ul>

<p>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.</p>

<p>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 <em>or</em> it runs forever. If it's very clean, then it goes to the first category. Otherwise it belongs to the second category.</p>

<p>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.</p>

<p>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.</p>

<blockquote>
  <p>The question is whether this "halting problem" can be solved.</p>
</blockquote>

<hr>

<p>Suppose I'm such a program, i.e. such a program exists.</p>

<p>Then there is a paradox. The question is:</p>

<blockquote>
  <p>Is there a program with a crossing structure?</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-11-05T20:40:38.507Z
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.
Zirui Wang
CC BY-SA 3.0
2011-11-05T20:48:24.623Z
I think this is more suitable for Math.SE.
Kaveh
CC BY-SA 3.0
2011-11-05T20:51:52.877Z
What if I write my answer in a CAPTCHA? I mean something humans can do but computers can't recognize.
Zirui Wang
CC BY-SA 3.0
2011-11-05T20:54:04.370Z
Hi, Kaveh. How are you? In terms of level, yes. But I thought the topic is on theoretical computer science. :p
Zirui Wang
CC BY-SA 3.0
2011-11-05T21:20:56.033Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-05T21:43:11.453Z
How about this? Two outputs: halt and "not halt or paradoxical".
Zirui Wang
CC BY-SA 3.0
2011-11-06T04:01:52.847Z
I don't understand the question: does the second choice mean that the machine chooses to not answer? Why can't a machine classify every input as being of the second class? In any case, you might be interested in "Byron Cook, Andreas Podelski, Andrey Rybalchenko: Proving program termination. Commun. ACM 54(5): 88-98 (2011)"
Anonymous
CC BY-SA 3.0
2011-11-06T06:28:28.873Z
I don't understand your modified version. How can you make a $t$ which simulate $p(i)$ and always halts? What if $p(i)$ does not halt, what will $t$ do?
Andrej Bauer
CC BY-SA 3.0
2011-11-06T06:29:55.237Z
Ok, if understand you correctly, your modified problem has just become very easy. Given $p$ and $i$, simulate $p(i)$. Whenever it halts, output "it halts". You are now semideciding halting, which is obviously doable.
Andrej Bauer
CC BY-SA 3.0
2011-11-06T07:54:20.263Z
@Anonymous: It can't put all programs into the second category. Consider a program that says 1) if you say yes on $(p,p)$, where $p$ is myself, then I halt. 2) if you say no or no answer on $(p,p)$, I will also halt. This program does not have the crossing structure (defined in my question) and it belongs to the first category. I think you don't get what I mean by a crossing structure. It's a static property about the code, not its behavior. And this is exactly my point. Let me try to illustrate in the next comment.
Zirui Wang
CC BY-SA 3.0
2011-11-06T08:03:59.113Z
(Cont) You see, the $p$ can run my code and see my verdict. So it can know exactly what my verdict is. But even if it contradicts *only* with my verdict, then it does not have the crossing structure. In order to have the crossing structure, it must contradict with every possibility. For example, a program that simulates me and says 1) if I say it halts and does not have the crossing structure, then it never halts or has the crossing structure; 2) If I say the opposite, it still never halts or has the crossing structure. This program does not have the crossing structure because of 2).
Zirui Wang
CC BY-SA 3.0
2011-11-06T08:09:44.377Z
(Cont) The point is that, once the program decides what to do, it cannot change. It can't contradict itself. When you design $P$, you can't pass the code of $P$ to $M$ and test the result. Unless, you have already designed $P$, that is, you have decided that $P$ will have the crossing structure. Then whatever $M$ does, you shouldn't be able to see the result of $M$ and change your code because you have decided on that before running $M$. This is a subtle distinction you have to distinguish.
Zirui Wang
CC BY-SA 3.0
2011-11-06T08:16:06.693Z
@Andrej: No, I'm not semideciding halting, as defined by you. Let's do the analysis. This is not what the program thinks. First there are programs that have the crossing structure and those that do not have. Then among those that do not, some halt while others don't. This two-level categorization is very clear, or should I say "recursive". That is, there is a yes-no answer to each of the two question. But because of expressiveness, I merged two cases. Now the distinction between categories are still clear-cut. This is to accommodate lack of expressiveness, not weakening the question.
Zirui Wang
CC BY-SA 3.0
2011-11-06T11:00:38.073Z
@Zirui Wang, please don't post questions which you know are not research level, they are off-topic for cstheory.
Kaveh
CC BY-SA 3.0
2011-11-07T12:14:44.360Z
@Kaveh: I mean **I**'m not research-level, not my question.
Zirui Wang
CC BY-SA 3.0
2011-11-07T12:44:26.587Z
Einstein: It does not need a thousand people to prove me wrong. It needs just one.
Zirui Wang
<computability><halting-problem>
Is halting that hard? [Yes]
Zirui Wang
# Is halting that hard? [Yes]

(Asked by: username_0 on 2011-11-05)

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.

**Tags:** computability, halting-problem

> **Comments:**
> **username_0**: 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.  
> **username_1**: I think this is more suitable for Math.SE.  
> **username_0**: What if I write my answer in a CAPTCHA? I mean something humans can do but computers can't recognize.  
> **username_0**: Hi, username_1. How are you? In terms of level, yes. But I thought the topic is on theoretical computer science. :p  
> **username_2**: 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.  
> **username_0**: How about this? Two outputs: halt and "not halt or paradoxical".  
> **username_3**: I don't understand the question: does the second choice mean that the machine chooses to not answer? Why can't a machine classify every input as being of the second class? In any case, you might be interested in "Byron Cook, Andreas Podelski, Andrey Rybalchenko: Proving program termination. Commun. ACM 54(5): 88-98 (2011)"  
> **username_4**: I don't understand your modified version. How can you make a $t$ which simulate $p(i)$ and always halts? What if $p(i)$ does not halt, what will $t$ do?  
> **username_4**: Ok, if understand you correctly, your modified problem has just become very easy. Given $p$ and $i$, simulate $p(i)$. Whenever it halts, output "it halts". You are now semideciding halting, which is obviously doable.  
> **username_0**: @username_3: It can't put all programs into the second category. Consider a program that says 1) if you say yes on $(p,p)$, where $p$ is myself, then I halt. 2) if you say no or no answer on $(p,p)$, I will also halt. This program does not have the crossing structure (defined in my question) and it belongs to the first category. I think you don't get what I mean by a crossing structure. It's a static property about the code, not its behavior. And this is exactly my point. Let me try to illustrate in the next comment.  
> **username_0**: (Cont) You see, the $p$ can run my code and see my verdict. So it can know exactly what my verdict is. But even if it contradicts *only* with my verdict, then it does not have the crossing structure. In order to have the crossing structure, it must contradict with every possibility. For example, a program that simulates me and says 1) if I say it halts and does not have the crossing structure, then it never halts or has the crossing structure; 2) If I say the opposite, it still never halts or has the crossing structure. This program does not have the crossing structure because of 2).  
> **username_0**: (Cont) The point is that, once the program decides what to do, it cannot change. It can't contradict itself. When you design $P$, you can't pass the code of $P$ to $M$ and test the result. Unless, you have already designed $P$, that is, you have decided that $P$ will have the crossing structure. Then whatever $M$ does, you shouldn't be able to see the result of $M$ and change your code because you have decided on that before running $M$. This is a subtle distinction you have to distinguish.  
> **username_0**: @Andrej: No, I'm not semideciding halting, as defined by you. Let's do the analysis. This is not what the program thinks. First there are programs that have the crossing structure and those that do not have. Then among those that do not, some halt while others don't. This two-level categorization is very clear, or should I say "recursive". That is, there is a yes-no answer to each of the two question. But because of expressiveness, I merged two cases. Now the distinction between categories are still clear-cut. This is to accommodate lack of expressiveness, not weakening the question.  
> **username_1**: @username_0, please don't post questions which you know are not research level, they are off-topic for cstheory.  
> **username_0**: @username_1: I mean **I**'m not research-level, not my question.  
> **username_0**: Einstein: It does not need a thousand people to prove me wrong. It needs just one.  

---

## 2 answers

### Answer by username_4 on 2011-11-05. Score: 3

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](http://en.wikipedia.org/wiki/Rice%27s_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.

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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.  

---

### Answer by username_5 on 2011-11-06. Score: 0

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.

> **Comments:**
> **username_0**: 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?  

---

