The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
23 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 ago in Theory of Computation by (119 points) | 23 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 ago by (497 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 infinite interval.
@arvin
0
okk thanku


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

38,009 questions
45,506 answers
131,660 comments
48,692 users