[Solved]: Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

Problem Detail: 

I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem.

What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow input~ \varepsilon$

Emptiness problem:
$E_{TM} = \{\langle M \rangle | ~M~ is~ a~ Turing~ machine~ and~ L(M)= \emptyset \}$
$E_{TM}$ is undecidable
$E_{TM}$ is recognizable but not co-turing-recognizable
$E_{TM}$ is not recognizable but co-turing-recognizable

Blank tape halting problem:
$H_0 = \{\langle M \rangle ~ |~ M~ is~ a~ Turing~ Machine~ that~ halts~ on~ input~ \varepsilon ~\}$
$H_0$ is undecidable
$H_0$ is recognizable but not co-turing-recognizable

any help is greatly appreciated

Asked By : Karl2011

Answered By : Denis Pankratov

Yes, they are different. $L(M)$ is the set of all inputs accepted by a Turing machine, so $E_{TM}$ asks if a Turing machine doesn't accept any inputs. $H_0$ asks whether a particular input (the empty string) is accepted. BTW, $E_{TM}$ should be co-Turing-recognizable, but not Turing-recognizable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52792

3.2K people like this

 Download Related Notes/Documents