4.4.4.7 The halting problem Quiz: AQA Computer Science, Unit 4

The 20 questions

1. What is the halting problem?

   • Sorting a list until it is complete, checking each element against the next one in line
   • Compressing a program so it runs faster
   • Counting the lines of a program
   • Determining whether a given program will eventually stop when given a particular input

2. The halting problem is best described as:

   • The problem of storing data in a database
   • The problem of finding the fastest sorting algorithm for any given list of items
   • The problem of drawing a program's flowchart
   • The unsolvable problem of determining whether any program halts on given input

3. What does the halting problem demonstrate?

   • All problems can be solved in linear time
   • Programs never need to be tested
   • Computers are always faster than people
   • Some problems cannot be solved by a computer

4. A non-computable problem is one that:

   • Always takes exactly one second
   • Cannot be solved by any algorithm
   • Is solved only by humans, who can always reason about a program output
   • Can only be solved in parallel

5. Which statement about deciding halting in general is correct?

   • A single algorithm decides halting for every program and every input, given enough time
   • It is only a problem for very long programs
   • No single algorithm decides halting for every program and input
   • It is solved by a faster computer

6. Does a program containing 'while True: pass' with no exit ever halt?

   • Yes, after one second
   • No
   • Yes, when the computer is switched off
   • It depends on the colour of the screen

7. Which of these programs clearly halts?

   • for i in range(10): print(i)
   • a function that calls itself with no base case
   • while True: print('again')
   • while x > 0: x = x + 1 with x starting at 1

8. Why does the halting problem matter for software testing?

   • It shows that testing is always impossible for small programs
   • No program can automatically verify that every program will terminate for all inputs
   • It makes all software testing completely unnecessary for every program being written today
   • It guarantees that every program halts

9. Is it possible to decide halting for one specific program?

   • Yes, for some individual programs halting can be determined
   • Only if the program is longer than 1000 lines
   • No, not for any program at all
   • Only for programs written in Python

10. Which of the following is a non-computable problem?

    • The halting problem
    • Sorting a list of numbers
    • Binary search on a sorted list
    • Bubble sort of five numbers

11. Which statement describes the significance of the halting problem for computation?

    • It proves that binary search is impossible
    • It proves that all computations are fast
    • It shows there are limits to what a computer can determine
    • It shows that computers can solve any problem

12. Which quantities does the halting problem's decision require as inputs?

    • The program and a particular input
    • The colour of the output
    • The date the program was written
    • The name of the programmer

13. Why is the halting problem called unsolvable?

    • It requires an infinite amount of paper
    • No algorithm decides halting correctly for all programs and all inputs
    • Its answer is always unknown to humans, who have never been able to study it
    • Programs are too long to read

14. Which quantity best describes a program that might run forever on some inputs?

    • Its halting behaviour is not decidable in general
    • Its running time is always exactly 1 second
    • It has no inputs at all
    • It is always a polynomial function

15. Which sensible response does a programmer take when a program might run forever on some input?

    • Assume it always halts because it was written by a careful and experienced person
    • Delete the entire program
    • Ignore the problem because computers never loop
    • Add timeouts or termination conditions, since no general test guarantees it

16. Which statement about the halting problem's result is correct?

    • It shows that there exist problems that no algorithm can solve
    • It shows that every problem can be solved by an algorithm, given enough computing power
    • It is only about hardware failures
    • It is a claim that no programs ever stop

17. What is the difference between an intractable problem and a non-computable problem?

    • An intractable problem has no solution at all, and a non-computable problem is solved quickly by computers
    • An intractable problem has a solution too slow to be practical, a non-computable one has none
    • They are the same concept
    • Intractable problems involve graphics only

18. Which best describes what the halting problem shows about computation?

    • Every question about programs can be answered by a faster program running on a faster computer
    • Some well-defined questions about programs cannot be answered by any program in all cases
    • Computation has no limits
    • Programs always halt if they are short

19. Which problem is non-computable?

    • Finding the largest of five numbers
    • Sorting a finite list of numbers
    • The halting problem for arbitrary programs and inputs
    • Binary search on a sorted array, which takes logarithmic time in the list length

20. What does it mean for a problem to be decidable?

    • The problem requires a graphical interface to solve
    • The problem can only be solved by a human expert who reasons about it slowly
    • The problem has no input at all
    • An algorithm exists that always gives the correct yes or no answer

Related quizzes

• Problem-solving and algorithms Quiz · 4.4.1.1 · 20 questions
• Abstraction Quiz · 4.4.1.3 · 20 questions
• Problem reduction and decomposition Quiz · 4.4.1.8 · 20 questions
• Composition Quiz · 4.4.1.10 · 20 questions
• Automation Quiz · 4.4.1.11 · 20 questions
• Finite state machines Quiz · 4.4.2.1 · 20 questions
• Regular expressions Quiz · 4.4.2.3 · 20 questions
• Backus-Naur Form and syntax diagrams Quiz · 4.4.3.1 · 20 questions
• Comparing algorithms Quiz · 4.4.4.1 · 20 questions
• Order of complexity Quiz · 4.4.4.3 · 20 questions