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

Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
emptinessproblemblankhaltingh_0tape

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#52792, answer score: 5

Revisions (0)

No revisions yet.