search
Log In
0 votes
131 views

Among II and III. Which one is decidable ? Please explain in detail.

in Theory of Computation
edited by
131 views
0
2. Decidable

3. Undecidable

1 Answer

0 votes
1. Decidable, membership problem for all language except RE is decidable

2. Decidable, run TM on all strings of length atmost k for k steps and accept if TM accepts at least one of the strings.

3. Undecidable, can be reduced to state entry problem.

Related questions

2 votes
0 answers
1
101 views
Consider the following statements: S1 : Let L be language, reversal of language L cannot contain any string present in β€˜L’ except β€˜βˆˆβ€™. S2 : Concatenation of two different language cannot be commutative until atleast one of them is β€˜Ξ¦β€™ or β€˜βˆˆβ€™. Which of the following is correct?
asked Jan 17, 2018 in Theory of Computation Sukhdip Singh 101 views
0 votes
2 answers
3
3 votes
1 answer
4
463 views
Consider the following languages A={<M>|M is a TM and |L(M)| >= 3} B={<M>|M is a TM that accepts some string} Which of the following is correct? (a.) A is decidable, B is partially decidable (b.) A is partially decidable, B is decidable (c.) Both A and B are decidable (d.) Both A and B are partially decidable Answer given : (d.) But how?
asked Jan 19, 2016 in Theory of Computation Utk 463 views
...