It seems that $ \text{NV}_{\text{TM}} = \{〈N〉: N \text{ a Turing-Machine and } L(N) ≠ ∅\}$ is not decidable.
Here is a proof:
Suppose that $\text{NV}_{\text{TM}}$ is decidable with the
Turing-Machine $R$.We can define for each Turing-Machine $M$ and each entry $w$ a
Turing-Machine $S_{M,w}$ as follow:$S_{M,w} :=$
- If $x \not= 0$, then reject $x$;
- If $x = 0$, then simulate $M$ on $w$ and accept if and only if $M$ accepts $w$
Consider now the Turing-Machine
$T :=$
- Input $〈M, w〉$:
- Construct the machine $S_{M,w}$ and product $〈S_{M,w}〉$;
- Simulate $R$ on the input $〈S_{M,w}〉$ :
- If $R$ accepts $〈S_{M,w}〉$ then accept $〈M, w〉$
- If $R$ rejects $〈S_{M,w}〉$ then reject $〈M, w〉$
I am a bit confused.
- How it is possible to simulate $R$ on the input $〈S_{M,w}〉$? For me, it is weird to simulate a Turing-Machine on another Turing-Machine. Is it related to Universal Turing Machine?
- The proof says nothing else. Supposing that $ \text{NV}_{\text{TM}}$ decidable should implies that $A_{TM}$ is also decidable. How with that proof can we say that $A_{TM}$ is dedicable (Contradiction)?
Best Answer
$R$ is a known Turing machine, so we don't have to use the universal Turing machine. We just switch to running $R$ on the input $\langle S_{M, w} \rangle$. We "call $R$ as a helper function", to use a programming analogy.
The idea is that $T$ decides halting problem. We know that $T$ always halts, since by assumption $R$ always halts.
Now note that $R$ accepts $\langle S_{M, w} \rangle$ iff $L(S_{M, w}) \neq \emptyset$ iff $\{0 | M$ halts on $w\} \neq \emptyset$ iff $M$ halts on $w$.
And note that $T$ accepts $\langle M, w \rangle$ iff $R$ accepts $S_{M, w}$ iff $M$ halts on $w$. So $T$ solves the halting problem.
But we know the Halting problem cannot be decided by any Turing machine. This is a contradiction.
Edit for more detail on "simulation":
Consider two Turing machines $T_1$ and $T_2$. We can "compose" the two machines to produce a machine $T$ which does the following:
The idea is as follows: our combined machine will have all the states which $T_1$ has, together with all the states $T_2$ has (WLOG assuming no overlap). The starting state will be the initial state of $T_1$. When we reach a halting state of $T_1$, instead of halting, we transition to the starting state of $T_2$.
We call $T$ the "composition" $T_2 \circ T_1$ because if $T_1$ computes function $f_1$ and $T_2$ computes function $f_2$, $T$ will compute $f_2 \circ f_1$.
Recall the steps given in the text:
This is the composition of two Turing machines. Let $T_1$ be the Turing machine which computes $\langle S_{M, w} \rangle$ from $\langle M, w \rangle$. Then the Turing machine we want to construct is $T = R \circ T_1$.