Lesson 4.4.4.7

4.4.4.7 The halting problem 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.4.7, The halting problem: 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 famous mathematician proved that the halting problem is algorithmically unsolvable?

    • Ada Lovelace
    • Charles Babbage
    • John von Neumann
    • Alan Turing

  2. How is the halting problem classified in terms of computability?

    • Linear problem
    • Tractable problem
    • Polynomial problem
    • Unsolvable problem

  3. What fundamental limit of computation does the halting problem demonstrate?

    • Hardware always fails
    • Polynomials are fast
    • Recursion is impossible
    • Non-computable problems exist

  4. What is a problem called if no algorithm can ever be written to solve it?

    • Tractable
    • Non-computable
    • Intractable
    • Exponential

  5. What classification is given to the halting problem?

    • Intractable
    • Polynomial
    • Non-computable
    • Tractable

  6. Will an infinite loop with no exit condition ever halt?

    • Yes
    • No
    • Only on error
    • Eventually

  7. Which type of iteration is guaranteed to finish in a set number of steps?

    • Definite iteration
    • Unbounded loop
    • Indefinite iteration
    • Infinite recursion

  8. What fundamental limit of computation is demonstrated by the halting problem?

    • Finite stack depth
    • Unsolvable problems exist
    • Hardware memory limits
    • Slow execution speeds

  9. Can halting be determined for specific individual programs?

    • Yes
    • Only theoretically
    • No
    • Never

  10. Which of these is a classic example of a non-computable problem?

    • Halting problem
    • Travelling salesperson
    • Graph colouring
    • Knapsack problem

  11. What does the halting problem demonstrate about computers?

    • Perfect error detection
    • Infinite processing power
    • Fundamental limits exist
    • Zero execution time

  12. What proof technique was used by Alan Turing to establish the halting problem?

    • Diagonalisation
    • Induction
    • Reduction
    • Brute force

  13. Why is the halting problem described as unsolvable?

    • Slow execution speed
    • No general algorithm
    • Excessive memory costs
    • Hardware limitations

  14. What term describes a problem for which no algorithm can be constructed?

    • Undecidable
    • Intractable
    • Exponential
    • Linear

  15. What term describes a problem that cannot be solved algorithmically by a computer?

    • Tractable
    • Intractable
    • Polynomial-time
    • Non-computable

  16. What does the proof of the halting problem establish?

    • Unsolvable problems exist
    • Algorithms are infinite
    • Hardware is unreliable
    • Compilers are flawed

  17. How do non-computable problems differ from intractable problems?

    • Slow polynomial time
    • No solution algorithm
    • Requires more memory
    • Runs too fast

  18. What major class of problems does the halting problem demonstrate?

    • Intractable problems
    • Non-computable problems
    • Exponential-time problems
    • Polynomial-time problems

  19. Which problem cannot be solved algorithmically for all possible inputs?

    • Bubble sort
    • Shortest path
    • Halting problem
    • Binary search

  20. What term describes a problem for which an algorithm always terminates with a correct yes or no answer?

    • Intractable
    • Undecidable
    • Tractable
    • Decidable

All AQA Computer Science quizzes