Halting Problem

Question

What is state entry problem? How Halting Problem can decide is it decidable or undecidable?

Comments

State entry problem: Given a turing machine, an input string and a state in that turing machine, tell whether the turing machine will enter to that state or not during the executing of the input string.

Halting problem can be reduced to this problem, and hence it is also undecidable.

Answer 1

State entry problem :- Let suppose we have a TM 'M' ,does our TM will ever enter(visit) some state 'q' during it's computation on any arbitrary input W.

In simple words will our TM ever enter a particular state for w ∈ ∑^* .

Halting problem has nothing to do with State entry problem , it's decidability and undecidability that's the concern.

Let  A ⊆_p B  from this reducibility we can claim two things

1) If A is undecidable then B will too.

2) If B is decidable then A will decidable too.

We basically use this concept to prove the decidability and undecidability of a language. and as HP is undecidable (RE but not REC) so if we can reduce this to state entry problem , we can then claim that SEP too undecidable.

Proof is simple , have a look here

http://www.cs.cornell.edu/courses/cs381/2002su/Materials/Homeworks/hw6/hw6-solns.pdf

Comments

while reducing this problem to halting problem why we are only focusing on the states those are halting state because this has been not specified that the state entry for the halting state only it can be any state…?

---

First of all we are not reducing this problem to halting problem – we are reducing halting problem to this problem thus proving that this problem is undecidable.