Consider the following problem $X$.

Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of $M$ on $w$ visit the state of $q$?

Which of the following statements about $X$ is correct?

- $X$ is decidable
- $X$ is undecidable but partially decidable
- $X$ is undecidable and not even partially decidable
- $X$ is not a decision problem

## 1 Answer

We have the TM $M$. Just make the state $q$ the final state and make all other final states non-final and get a new TM $M'$. Give input $w$ to $M'$. If $w$ would have taken $M$ to state $q$ (yes case of the problem), our new TM $M'$ would accept it. So, the given problem is partially decidable.

If $M$ goes for an infinite loop and never reaches state $q$ (no case for the problem), $M'$ cannot output anything. This problem is the state entry problem, which like word accepting problem and halting problem is undecidable.

### 15 Comments

No, you can't use rice theorem here as rice theorem is applicable on the properties of languages. Here in the question this is not a property of a language.

http://gatecse.in/rices-theorem/

Refer to this link.

Also, if the property of TM is given then try to reduce it into the property of some language if you can do that then you can apply Rice theorem. But it is not possible in every case.

@Arjun sir ..is my reasoning correct?

i can reduce the halting prblm into the given GATE _2001 problem.. let the state q=final state..

$\Rightarrow$give any word w on machine $M$

$\Rightarrow$do machine visit this state?

**YES**

$\Rightarrow$Word will halt in final state and hence will be accepted .

**NO**

$\Rightarrow$if the word does not visit q that means this word will not be accepted by machine M .

Hecne i have reduced

$\text{HALTING PROBLEM <p Gate 2001 problem}$

.as we know Halting problem is Harder so is GATE 2001 prblm.

as we know Halting problem is semidecidable so is GATE 2001 prblm.

For yes cases yes as it prints Q

For no cases doesn't print anything.