The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
154 views

Please tell whether the following is Decidable, Semi-decidable or Undecidable
1. The control of a turing machine moves right exactly n times
2. The control of a turing machine moves right atmost n times
3. The control of a turing machine moves right atleast n times
4. A turing machine accepts strings of length exactly "n"
5. A turing machine accepts strings of length atleast "n"
6. A turing machine accepts strings of length atmost "n"
7. A turing machine visits exactly n states
8. A turing machine visits atleast n states
9. A turing machine visits atmost n states
10. A turing machine replaces the characters on the tape exactly n times
11. A turing machine replaces the characters on the tape atleast n times
12. A turing machine replaces the characters on the tape atmost n times

asked in Theory of Computation by Active (3.1k points)
edited by | 154 views
+2
1,2,3,7-12 are decidable , because all are property of TM and also not property of TM language

4 and 5 turing recognizable

6 is not even turing recognizable
0
Plz explain this with reasoning I find this topic very difficult to understand
+1
Shouldn't  6th answer be recursively enumerable
0
Yes! 6th should be RECURSIVELY ENUMERABLE.

4 and 6 are RE.

5th is NOT RE.
0
according to me whether TM has 'n' states or not is decidable, But TM visits state 'n' or not is undecidable.
0

Please log in or register to answer this question.

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

42,572 questions
48,562 answers
155,427 comments
63,581 users