patternMinor
Proof (by contradiction) of the emptiness problem
Viewed 0 times
emptinessproblemthecontradictionproof
Problem
I fail to understand the proof of the Emptiness Problem
$E_{TM} = \{\langle M \rangle | M $ is a TM and $L(M) = \emptyset\}$
1) Use the description of $M$ and $w$ to construct $M_1$, which on Input $x$ behaves as follows:
2) Run $R$ on input $\langle M_1\rangle$
3) If $R$ accepts, reject; if $R$ rejects, accept
I do understand the basic idea of a reduction and in particular the reduction of $A_{TM}$ to $Halt_{TM}$, however,
-
I do not see how $E_{TM}$ could be used as a subroutine to solve $A_{TM}$. The whole construction of $M_1$ confuses me a lot. To me it looks like $M_1$ is just like a filter that rejects everything except $w$
-
But why does $M_1$ even have to check if $x$ equals $w$? As soon as $S$ is fed with a particular pair $\langle M,w\rangle$, $x$ will be equal to $w$, no? how can it be anything different than $w$?
$E_{TM} = \{\langle M \rangle | M $ is a TM and $L(M) = \emptyset\}$
1) Use the description of $M$ and $w$ to construct $M_1$, which on Input $x$ behaves as follows:
- If $x \neq w$, reject
- If $x = w$, run $M$ on input $w$ and accept if $M$ does
2) Run $R$ on input $\langle M_1\rangle$
3) If $R$ accepts, reject; if $R$ rejects, accept
I do understand the basic idea of a reduction and in particular the reduction of $A_{TM}$ to $Halt_{TM}$, however,
-
I do not see how $E_{TM}$ could be used as a subroutine to solve $A_{TM}$. The whole construction of $M_1$ confuses me a lot. To me it looks like $M_1$ is just like a filter that rejects everything except $w$
-
But why does $M_1$ even have to check if $x$ equals $w$? As soon as $S$ is fed with a particular pair $\langle M,w\rangle$, $x$ will be equal to $w$, no? how can it be anything different than $w$?
Solution
- $M_1$ rejects everything, including $w$, unless $M$ accepts it (crucial). $M_1$ will then be a machine that always rejects, if and only if $M$ rejects $w$.
- The white box treats $M$ and $w$ as constants. They are still something that $S$ received as input, and we know that.
- $R$ is a hypothetical machine that decides if its input is a machine that always rejects.
- $S$ will receive unknown $\langle M,w \rangle$ as its input. Should $R$ work as intended, then $S$ in fact solves the general problem of deciding if $M$ accepts $w$, which is exactly $A_{TM}$.
- It has been proven that $A_{TM}$ is not decidable.
Therefore,
-
$R$ cannot exist.
Our reference question has more information on the subject. You may find particularly interesting to see how this kind of proof can be generalized (look for Rice's theorem).
Context
StackExchange Computer Science Q#66282, answer score: 3
Revisions (0)
No revisions yet.