Why cannot we enumerate all Turing machines that have no fixed point?

Question

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.

Answer 1

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.

Answer 2

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.