The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
55 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.1k points) | 55 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 Active (3.4k 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


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

41,071 questions
47,669 answers
147,407 comments
62,387 users