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

4 and 5 turing recognizable

6 is not even turing recognizable

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,260 answers

182,165 comments

67,679 users