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 element is NOT part of the basic structure of a Turing machine as described at A level?

    • An infinite tape of marked-off squares
    • A finite set of states
    • A sensing read-write head
    • A graphical user interface for entering input

  2. What is a halting state in a Turing machine?

    • A state with no outgoing transitions, at which computation stops
    • A state entered only when the tape is completely full
    • The state in which the machine begins computation
    • A state that writes a blank symbol to every square

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

    • The state that always moves the head to the left
    • The state reached once the whole tape has been read
    • The state with no outgoing transitions
    • The state in which computation begins

  4. How far does the read-write head of a Turing machine move in a single step?

    • The entire length of the tape in one move
    • Any number of squares chosen by the program
    • Two squares in alternate directions
    • One square along the tape, left or right

  5. What is meant by the alphabet of a Turing machine?

    • The list of halting states shown in the diagram
    • An infinite set of symbols already written on the tape
    • The set of every state the machine is able to enter
    • A finite set of symbols the machine can read and write

  6. What does the transition function of a Turing machine take as its input?

    • The whole tape contents, along with the clock speed used
    • Only the number of squares already visited so far
    • The next state and the symbol that is to be written
    • The current state and the symbol under the read-write head

  7. A Turing machine can be viewed as a computer with which of the following?

    • A single fixed program
    • Many programs stored in memory at once
    • A program that rewrites its own rules at runtime
    • An unlimited number of read-write heads

  8. Why are Turing machines and the Universal Turing machine important in computer science?

    • They replace the need for any programming language
    • They describe the fastest possible hardware design for general computing
    • They provide a formal model that defines what is computable
    • They show every problem can be solved in polynomial time

  9. A Universal Turing machine is able to do which of the following?

    • Run with an unlimited number of states active at the same time
    • Always halt within a fixed number of steps, whatever the input is
    • Simulate any other Turing machine when given that machine's description
    • Run only one hard-coded program and never read a description

  10. A Turing machine has a state P with the rule: reading 1, write 0, move left, go to state Q. The head is on a square holding 1 in state P. What happens?

    • The square stays 1, the head moves right, and the machine enters state P
    • The square becomes 0, the head moves one square right, and the machine stays in state P
    • The square becomes 0, the head moves one square left, and the machine enters state Q
    • The machine halts at once without changing the tape

  11. A Turing machine starts in state S on a blank tape. Its only rule is: in state S reading blank, write 1, move right, stay in state S. What happens?

    • It moves left and halts on the first square it reads
    • It halts after four squares because the tape has four squares
    • It never halts, writing 1s on successive squares to the right
    • It halts after writing a single 1 on the first square

  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. A transition function is written as delta(S, 0) = (T, 1, R). What does this mean?

    • In state S reading 0, write 1, move left and go to state T
    • In state S reading 1, write 0, move right and go to state T
    • In state S reading 0, write 1, move right and go to state T
    • In state T reading 1, write 0, move left and go to state S

  14. An arrow from state X to state Y in a state transition diagram is labelled 0/1,R. What does this label mean?

    • Read 1, write 0, move the head right, then move to state X
    • Read 0, write 1, move the head right, then move to state Y
    • Read 0, write 1, move the head right, then stay in state X
    • Read 0, write 1, move the head left, then move to state Y

  15. A tape holds 0 1 with the head on the first square. In state A reading 0, the rule writes 0, moves right and enters the halting state H. What is the final state of the tape and head?

    • Tape 0 1, head on the second square, machine halted in H
    • Tape 0 0, head off the tape to the left, machine still running
    • Tape 0 1, head on the first square, machine still running
    • Tape 1 1, head on the first square, machine halted in H

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

    • Tape 0 1 0, head on square 1, halted
    • Tape 1 1 0, head on square 2, halted
    • Tape 1 1 0, head on square 1, halted
    • Tape 1 0 0, head on square 3, halted

  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. Why does the specification stress an infinite tape when real computers have finite memory?

    • The tape is infinite only so that the head never has to move to the left at any stage of the run
    • An infinite tape guarantees that every program halts in a finite number of steps for any given input
    • An unbounded tape lets the model represent any computation needing unlimited memory, so it defines computability
    • Real computers have infinite memory, so the model matches them exactly in every practical case

  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