Lesson 4.4.5.1

4.4.5.1 The Turing machine Quiz: AQA Computer Science, Unit 4

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.4.5.1, The Turing machine: 20 multiple choice questions for the AQA Computer Science (7517), Unit 4: Theory of computation, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. Which of these is NOT a component of a basic Turing machine?

    • Read-write head
    • Infinite tape
    • Finite state set
    • Graphical user interface

  2. What characterizes a halting state in a Turing machine state transition diagram?

    • No outgoing transitions
    • Self-loop transition
    • No incoming transitions
    • Multiple start arrows

  3. What is the purpose of the start state in a Turing machine?

    • Where tape terminates
    • Where output prints
    • Where computation stops
    • Where computation begins

  4. How far can the read-write head move in a single transition step?

    • To tape end
    • Two squares
    • Any distance
    • One square

  5. What is the alphabet of a Turing machine?

    • List of rules
    • Sequence of bits
    • Set of states
    • Set of symbols

  6. What inputs does a Turing machine transition function require?

    • State only
    • Tape length
    • Symbol only
    • State and symbol

  7. What key component does a standard Turing machine use to store data and instructions?

    • Infinite tape
    • Random access memory
    • Registers only
    • Solid state drive

  8. Why are Turing machines fundamentally important in computer science?

    • Eliminate syntax errors
    • Optimize memory storage
    • Define computable problems
    • Speed up execution

  9. What can a Universal Turing machine do when given a machine description?

    • Expand tape infinitely
    • Compile machine code
    • Simulate that machine
    • Halt all loops

  10. Rule: delta(P, 1) = (Q, 0, L). In state P reading 1, what symbol is written?

    • 1
    • P
    • 0
    • Q

  11. In state S reading blank, a rule writes 1, moves right, and stays in S. What occurs?

    • Moves left endlessly
    • Erases tape
    • Never halts
    • Halts immediately

  12. A tape holds 1 1 1 followed by blanks, and the head starts on the first 1. Rule: in state S, reading 1 writes 1 and moves right; reading blank halts. How many squares does the head visit, including the start square?

    • 3
    • 2
    • 4
    • 5

  13. In the transition function delta(S, 0) = (T, 1, R), what state is entered next?

    • 1
    • 0
    • T
    • S

  14. In the Turing machine transition label 0/1, R, what does 0 represent?

    • Symbol written
    • Symbol read
    • Next state
    • Head direction

  15. Tape shows 0 1, head on 0. Rule writes 0, moves right, halts. Which symbol is under the head?

    • 1
    • None
    • Blank
    • 0

  16. Tape is 0 1 0 with head on square 1. Reading 0 writes 1 and moves right. What is the updated tape?

    • 0 1 0
    • 1 1 0
    • 0 0 0
    • 1 0 0

  17. A tape holds 1 1 1 with the head on square 1. Rule: in state S, reading 1 writes 0, moves right and stays in S; reading blank halts. How many squares still hold 1 after the machine halts?

    • 0
    • 2
    • 3
    • 1

  18. A tape holds 1 0 1 with the head on square 1. Rule: in state S, reading 1 writes 0 and moves right; reading 0 writes 1 and moves right; both stay in S, and reading blank halts. What is the final tape?

    • 0 1 1
    • 1 0 1, unchanged
    • 0 0 0
    • 0 1 0

  19. What does the infinite tape in a Turing machine define?

    • Hardware efficiency
    • Physical memory size
    • What is computable
    • Execution speed

  20. Squares 1 and 2 hold 1s, with blanks elsewhere and the head on square 1. Rules: S reading 1 moves right and stays in S; S reading blank writes 1, moves left and enters T. T reading 1 writes 0, moves left and stays in T; T reading blank halts. What are squares 0 to 3?

    • blank, 1, 1, 1
    • blank, 0, 1, 1
    • blank, 0, 0, 1
    • 1, 1, 0, 1

All AQA Computer Science quizzes