← All topics
Quiz: Turing Machines: questions with answers
10 questions, each with the answer and a short explanation.
Take the timed quiz + get a certificate →- Q1. What can a Turing machine do that a pushdown automaton cannot?
- Q2. In the increment demo, what is 111 + 1?
- Q3. Which language did the second TM accept that no PDA can?
- Q4. Compared with deterministic TMs, nondeterministic TMs recognise:
- Q5. What does the Church–Turing thesis state?
- Q6. In δ(q, a) = (p, b, R), what does the machine do?
- Q7. Which of these is the key difference between a Turing machine's tape and a PDA's stack?
- Q8. A multi-tape Turing machine compared with a single-tape one is:
- Q9. What does a universal Turing machine take as input?
- Q10. A TM decides a language L when: