The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
84 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 (2.1k points) | 84 views
+2
i think it should be a B.

1 Answer

+1 vote
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 (8.1k 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
49,412 questions
53,594 answers
185,832 comments
70,878 users