The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

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

+42 votes

Best answer

$X$ is undecidable but partially decidable.

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.

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.

0

Yeah.. But what if the state isn't a final state...? Shouldn't we think of that case too? I understand that this reduces to halting problem when the state q is final.. What if it isn't?

0

state q in M need not be final state. It is just that in our new machine M' we make q final and all other nonfinal.

M' works the same way as M (same rules) but in M' if it ever goes to q then we get an answer YES.

M' works the same way as M (same rules) but in M' if it ever goes to q then we get an answer YES.

+2

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.

0

@arjun sir , what can we say about '' no case of the problem '' in which original M does not enters the state "q", and halts and rejects the w on some other state I think in that case new machine M' will also haltSand reject w ... then what we say about its decidability ??

0

@sir can we say that if the above question was decidable then halting problem would be decidable?

I mean to say that we can reduce Halting problem to above problem(so called state entry problem).

Right?

I mean to say that we can reduce Halting problem to above problem(so called state entry problem).

Right?

0

.halting problem of turing machine is undecidable but partially deciadble hence this problem can be redu ced from halting problem so is undecidable put partially decidable

0

@larnav u can design a universal turing machine which accepts a turing machine and a string input and say yes if it halts because it can wait till it halts and say yes if it reaches final state but if it doesn't halt or goes into an infinite loop the universal turing machine cannot say no so we can say yes or go into infinite loop or wait forever hence it is semi decidable and undecidable as every semi decidable is also undecidable

0

@Arjun sir. I think we also need to set all transitions of state q back to q in the new TM. Because it might be possible that the TM visits state q, but moves on and stops at any other state. This will give a NO answer. But the answer of our original question is YES. right??

0

@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.

0

Can we think about in this way, such that whenever it goes to a state it prints out the state. So if it ever visit Q, then prints Q. But if it goes on infinite loop , then it won't print the Q or even it it finite times loop and never goes to Q, then never output Q. So this is semi decidable.

For yes cases yes as it prints Q

For no cases doesn't print anything.

For yes cases yes as it prints Q

For no cases doesn't print anything.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,713 questions

46,750 answers

140,552 comments

58,385 users