Simulate a Turing-Machine over a Turing Machine

decidabilitysimulationturing-machines

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} :=$

  1. If $x \not= 0$, then reject $x$;
  2. If $x = 0$, then simulate $M$ on $w$ and accept if and only if $M$ accepts $w$

Consider now the Turing-Machine

$T :=$

  1. Input $〈M, w〉$:
  2. Construct the machine $S_{M,w}$ and product $〈S_{M,w}〉$;
  3. Simulate $R$ on the input $〈S_{M,w}〉$ :
  4. If $R$ accepts $〈S_{M,w}〉$ then accept $〈M, w〉$
  5. If $R$ rejects $〈S_{M,w}〉$ then reject $〈M, w〉$

I am a bit confused.

  1. 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?
  2. 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:

  1. Run $T_1$ on the input.
  2. Run $T_2$ on whatever is left on the tape from the execution of $T_1$. If $T_2$ is an accepting/rejecting machine rather than just a machine which computes an output on the tape, then accept/reject as $T_2$ does.

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:

  1. From $\langle M, w \rangle$ construct $\langle S_{M, w} \rangle$.
  2. Execute $R$ on the input $\langle S_{M, w} \rangle$. Accept iff $R$ accepts; reject iff $R$ rejects.

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$.

Related Question