Decidability

Question

Decide whether or not the state $q$ is ever entered when $M$ is applied to string $w$.

Can somebody explain the solution.

Comments

u can take help from this link https://gateoverflow.in/153560/halting-problem

Answer 1

I assume by M you are talking about a Turing machine.

If M is a Turing machine then we can just run M on given string w.

So the given problem is semi - decidable or Turing recognizable.

That is the machine can say 'yes' if the state q is entered on the given string w, but if it never enters the state the machine cannot say 'no' for sure.

This is the famous state entry problem.

Here is a link which proves that :

https://users.cs.duke.edu/~rodger/courses/cps140/lects/sectdecideH.pdf