search
Log In
36 votes
4.5k views

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?

  1. $X$ is decidable
  2. $X$ is undecidable but partially decidable
  3. $X$ is undecidable and not even  partially decidable
  4. $X$ is not a decision problem
in Theory of Computation
edited by
4.5k views

1 Answer

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

edited by
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.
0
Can we use the rices theorem on this ? anyone please explain....
8

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
what is the difference between undecidable and partially decidable problems?
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?
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

@Venkat Sai Yes Sir, you're right. My Bad. Thank you!

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.
0
0
Why is this not undecidable ? From what I understand there is still a possibility that M' goes into loop before reaching state q, so we can't even be sure that M' will accept even if w belongs to M'.
Answer:

Related questions

23 votes
2 answers
1
1.7k views
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
asked Sep 15, 2014 in Theory of Computation Kathleen 1.7k views
16 votes
4 answers
2
2.8k views
Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$ Which of the languages are regular? Only $L1$ and $L2$ Only $L2, L3$ and $L4$ Only $L3$ and $L4$ Only $L3$
asked Sep 14, 2014 in Theory of Computation Kathleen 2.8k views
15 votes
2 answers
3
1k views
Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.
asked Sep 15, 2014 in Theory of Computation Kathleen 1k views
23 votes
2 answers
4
1.6k views
Construct DFA's for the following languages: $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$ $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has an odd number of a's and an odd number of b's } \right\} $
asked Sep 15, 2014 in Theory of Computation Kathleen 1.6k views
...