0 votes 0 votes Decide whether or not the state $q$ is ever entered when $M$ is applied to string $w$. Can somebody explain the solution. Theory of Computation theory-of-computation turing-machine + – Saurav asked Mar 19, 2018 • retagged Mar 25, 2018 by Sukanya Das Saurav 321 views answer comment Share Follow See 1 comment See all 1 1 comment reply akshat sharma commented Mar 19, 2018 reply Follow Share u can take help from this link https://gateoverflow.in/153560/halting-problem 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 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 ArjuMlu answered Mar 19, 2018 • edited Mar 19, 2018 by ArjuMlu ArjuMlu comment Share Follow See all 0 reply Please log in or register to add a comment.