748 views
2 votes
2 votes
Let <M> be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M> | M is TM on input w will visit some state P}.
The language L is
(a) Decidable
(b) Undecidable but partially decidable
(c) Undecidable and not even partially decidable
(d) Not a decision problem

2 Answers

1 votes
1 votes
it is c i think.

because decidable means either yes or no . so i dont think there is any terms as partial decidable

CORRECT ME IF I AM WRONG.

it is undecidable because we never know whether there is a state present in loop
0 votes
0 votes

It should be option “b” Undecidable but partially decidable. Because when the TM goes to some state it will either accept + halt or reject+ halt/loop. Even on rejection it can go to infinite loop and in doing so it will definitely go to some state. Hence option “b” should be correct. 

edited by

Related questions