The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
126 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 (1.7k points)
edited by | 126 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
0
Shouldn't  6th answer be recursively enumerable

Please log in or register to answer this question.



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

39,437 questions
46,622 answers
139,340 comments
57,001 users