2
$\begingroup$

The language

$$ L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\} $$

($w$ is an encoding of a DTM, $M_w$ is the respective DTM.)

is not decidable, according to Rice's theorem. However, it is recursively enumerable: an NTM simply chooses an $x$ for which the condition is fulfilled non-deterministically.

Consider the very similar language

$$ L_2 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) \neq x\} $$

Rice's theorem argues that this is undecidable, but neither is it semi-decidable according to my sources.

Why can't we argue for $L_2$ as we did for $L_1$, stating that an NTM chooses the input $x$ non-deterministically, the condition is fulfilled, $L_2 \in \mathsf{RE}$?

The proof that $L_2 \not\in \mathsf{RE}$ performs the reduction $\overline H \leq L_2$, where $H$ is the halting problem. I understand this proof by reduction, but to me, it seems contradictory to the argument for recursive enumerability I give above.

$\endgroup$
  • $\begingroup$ "an NTM chooses the input $x$ non-deterministically, the condition is fulfilled". Really? When can you claim it is fulfilled or not fulfilled supposing the NTM is stilling running whenever you checked (but you cannot know that fact beforehand)? $\endgroup$ – Apass.Jack Feb 26 at 21:30
  • $\begingroup$ @Apass.Jack My thinking goes like this: if you can have an NTM, which guesses an $x$, runs $M_w(x)$ and determines that $M_w(x) = x$, then you can just as well have an NTM, which guesses an $x$, runs $M_w(x)$ and determines that $M_w(x) \neq x$. There must be a flaw in my reasoning, I can't spot it, though. $\endgroup$ – cadaniluk Feb 26 at 21:35
  • $\begingroup$ @Apass.Jack It all relies on non-determinism to me. If I chose a DTM in place of an NTM to run $M_w(x)$ for all possible inputs, it would be game over if $M_w(x)$ didn't halt because that would prevent subsequent runs of $M_w(x)$ with different $x$es. I conclude that an NTM can guess what inputs halt and which do not. Hence, $L_2$ should also be recursively enumerable. Again, I must be wrong somewhere, but I don't see where. $\endgroup$ – cadaniluk Feb 26 at 21:39
2
$\begingroup$

Because we cannot find, given a NTM $N$ and an input $x$, whether $N$ fulfills the condition $N(x)\not= x$ in any given finite amount of time. More precisely, we cannot enumerate all pairs $(N,x)$ such that $N(x)\not= x$, although we can enumerate all pairs $(N,x)$ such that $N$ halts on $x$ and $N(x)\not= x$.


Think for a moment. When can you consider $(N,x)$ fulfills the requirement $N(x)\not=x$?

  • We run $N$ with input $x$ for some time and it stops. If it does not output $x$, great, we have found one.
  • We run $N$ with input $x$. However $N$ does not stop yet. It seems $N$ just won't stop. We want very much to say $(N,x)$ does not fulfill that requirement; however, there is no moment we can be sure of that. $N$ is just running at all times. If we conclude $(N,x)$ does fulfill the requirement at some moment, it can happen $N$ will stop at the next moment, outputting $x$. Because of this possibility, we will never add $(N,x)$ when $N$ never stops on input $x$, even though $(N,x)$ does satisfy the requirement.

Note this is vastly different from the other case. When can we consider $(N,x)$ fulfils the requirement $N(x)=x$?

  • We run $N$ with input $x$ for some time and it stops. If it does output $x$, great, we have found one.
  • We run $N$ with input $x$. However $N$ does not stop yet. Fine, we just do not consider $(N,x)$ fulfils the requirement yet. Continue running $N$.

You might argue that NTM $N$ can guess $x$ such that $N(x)$ will halt and output $y\not=x$. So we will find one such $N$. There is no problem in that.

However, consider the case when $N$ never stops on every input. Now, imagine the exact moment you consider that $N$ fulfills the condition that $N(x)\not= x$ for some $x$, using any algorithm. What is known to you at that moment? All you know is that $N$ has not stopped yet on any input. That, however, does not exclude the possibility that $N$ might stop later on for all inputs along all paths, always outputting the input. We can never exclude that possibility, forever. (More precisely, we can exclude that possibility for some $N$ for some inputs. However, there is no algorithm can determine that possibility for all $N$.)

If I chose a DTM in place of an NTM to run $M_w(x)$ for all possible inputs, it would be game over if $M_w(x)$ didn't halt because that would prevent subsequent runs of $M_w(x)$ with different $x$es.

It would also be game over if $M_w(x)$ will not halt for all $x$. Your $NTM$ will be running forever without ever outputting anything. That $(M,x)$ is in $L_2$ but your algorithm cannot claim it is in $L_2$ since there is no moment when the algorithm is able to claim that.


The explanation above is meant to be a way to understand the situation. A rigorous proof is still needed to confirm the conclusion mathematically (or "compute sciencely"). Since you have known a rigorous proof, I will not provide one here.

$\endgroup$
  • $\begingroup$ This is somewhat hairsplitting to beginners. It trips me up from time to time as well. Another way to understand is that in general, we cannot enumerate a set whose members includes those situations where TM will run forever. (A much general approach is embodied in the field of arithmetic hierarchy) $\endgroup$ – Apass.Jack Feb 26 at 23:08
  • $\begingroup$ Another way to understand is its similarity to the halting problem. The set of pairs ⟨M,x⟩ where $M$ halts on $x$ is recursively enumerable but set of pairs ⟨𝑀,x⟩ where $M$ does not halts on $x$ is not. You can check why an argument similar to your NTM will fail on the latter case. $\endgroup$ – Apass.Jack Feb 26 at 23:20
1
$\begingroup$

The NTM can recognize, not determine (because if no such $x$ exists, the NTM would not halt), $M_w(x)=x$, because if such an $x$ exists, the NTM would halt finally (and accept $\langle M_w, x\rangle$).

The NTM cannot recognize $M_w(x)\neq x$, because even if such an $x$ exists, the NTM may not halt.

If you change $L_2$ to $\{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon \color{red}{M_w(x)\text{ halts }}\text{and } M_w(x) \neq x\}$, then it becomes recognizable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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