Theory of Computation – Multiple Choice Questions (MCQs)

1. 13. What is a Turing Machine (TM)?

   • A. A finite automaton with a tape of infinite length
   • B. A pushdown automaton without a stack
   • C. A computational model that can simulate any algorithm
   • D. A model of computation less powerful than a finite automaton

2. 14. What is the tape in a Turing Machine?

   • A. A finite storage medium
   • B. An infinite storage medium divided into cells
   • C. A read-only input medium
   • D. A write-only output medium

3. 15. What is the tape head in a Turing Machine?

   • A. A device that reads input symbols only
   • B. A device that can read and write symbols on the tape and move left or right
   • C. A device that controls the finite control
   • D. A device that marks the end of the tape

4. 16. What are the states in the finite control of a Turing Machine?

   • A. The input symbols
   • B. The possible configurations of the tape
   • C. The finite set of states the machine can be in
   • D. The output symbols

5. 17. What is an accepting state in a Turing Machine?

   • A. A state in which the machine halts and rejects the input
   • B. A state in which the machine continues processing indefinitely
   • C. A state in which the machine halts and accepts the input
   • D. Any state that is not the initial state

6. 18. What is a rejecting state in a Turing Machine?

   • A. A state in which the machine halts and accepts the input
   • B. A state in which the machine continues processing
   • C. A state in which the machine halts and rejects the input
   • D. The initial state

7. 19. Which languages are accepted by Turing Machines?

   • A. Regular languages
   • B. Context-free languages
   • C. Context-sensitive languages
   • D. Recursively enumerable languages

8. 20. What is a recursively enumerable language?

   • A. A language that can be accepted by a Turing Machine
   • B. A language that can be decided by a Turing Machine
   • C. A language generated by a context-free grammar
   • D. A regular language

9. 21. What is a recursive language?

   • A. A language for which there exists a Turing Machine that halts on every input and accepts the strings in the language and rejects the strings not in the language
   • B. A language accepted by an NFA
   • C. A language generated by a regular expression
   • D. A language accepted by a PDA

10. 22. What is the Church-Turing thesis?

    • A. The claim that any function computable by a human using pen and paper can also be computed by a Turing Machine
    • B. The claim that Turing Machines are not powerful enough to model all computation
    • C. The claim that all computational models are equivalent in power to finite automata
    • D. The claim that all languages are recursively enumerable

11. 23. What is undecidability?

    • A. The property of a problem for which no Turing Machine can be constructed that always halts and gives a correct yes or no answer for every possible input instance
    • B. The property of a problem that can be solved in polynomial time
    • C. The property of a language that is not recursively enumerable
    • D. The property of a grammar that is ambiguous

12. 24. Which of the following problems is known to be undecidable?

    • A. The Halting Problem
    • B. Sorting an array
    • C. Searching in a sorted list
    • D. Multiplying two integers