The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
71 views
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
asked in Theory of Computation by Active (1.4k points) | 71 views
+2
i think it should be a B.

1 Answer

0 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
answered by Loyal (6.2k points)
+2
B.
D< PD < UD (< =proper subset).
to be more precise i think its PD because they have said that it will move to some state on w means there is a point when it will halt for w but we don't know when that string will come it may be after an infinite interval.
0
okk thanku

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,003 questions
51,323 answers
177,490 comments
66,668 users