The Gateway to Computer Science Excellence
0 votes

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

in Theory of Computation by Active (2.4k points)
edited by | 67 views
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.
by Active (2.2k points)

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
50,666 questions
56,170 answers
94,047 users