HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Proof (by contradiction) of the emptiness problem

Submitted by: @import:stackexchange-cs··
0
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:

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