Skills101
← All practice quizzes

Quiz: Turing Machines

5 questionsNo time limitPass: 60%+10 XP on first pass

The Turing machine explained simply: tape, head, states and transitions, a Python simulator running machines for binary increment and aⁿbⁿcⁿ, why multi-tape and nondeterministic variants add no power, universal Turing machines, and the Church–Turing thesis.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    What can a Turing machine do that a pushdown automaton cannot?

  2. Question 2

    In the increment demo, what is 111 + 1?

  3. Question 3

    Which language did the second TM accept that no PDA can?

  4. Question 4

    Compared with deterministic TMs, nondeterministic TMs recognise:

  5. Question 5

    What does the Church–Turing thesis state?