Computable problems and the Halting problem

Overview

Recall questions on the Halting problem, why it cannot be settled by simply running the program, and the difference between non-computable and merely intractable.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What does it mean to say that some problems cannot be solved algorithmically?

   Model answer

   It means there are problems for which no algorithm exists that will always produce the correct answer in a finite number of steps — not merely that nobody has found one yet, nor that the known algorithms are too slow, but that no such algorithm can exist. These are called non-computable problems.

2. 2

   Distinguish a non-computable problem from an intractable one.

   Model answer

   An intractable problem has an algorithm that gives the right answer, but its running time grows faster than any polynomial, so it is only usable on small inputs. A non-computable problem has no algorithm at all, so no amount of time, memory or processor speed will help. Intractability is a limit on what can be done in practice; non-computability is a limit on what can be done in principle.

3. 3

   Describe the Halting problem.

   Model answer

   The Halting problem asks for a single algorithm that, handed the description of any program together with any input for that program, would always report correctly whether it eventually stops or instead runs forever. Turing proved that no such algorithm can be written: the problem is unsolvable, not merely difficult. It is the general case that fails — plenty of individual programs can be shown by inspection to halt.

4. 4

   Why can you not settle the Halting problem simply by running the program and watching?

   Model answer

   Because while the program is still running you cannot tell which of the two cases you are in. If it stops, you have your answer for that case. But if it has not stopped yet, you cannot tell whether it will stop in another second, in a hundred years, or never — and there is no point at which continuing to wait becomes conclusive. Running the program can confirm halting but can never confirm non-halting.

5. 5

   What is the significance of the Halting problem for computation?

   Model answer

   Its significance is that computation has limits of principle, not merely limits of speed. Certain problems admit no algorithmic solution at all, so no computer can solve them — however fast the machine and however long it is left running. That rules out, for instance, a perfect general tool for detecting infinite loops in submitted code, and it makes establishing which problems are computable in the first place a genuine part of computer science.

6. 6

   What practical consequence does the Halting problem have for software tools?

   Model answer

   No compiler, debugger or analysis tool can be written that always decides correctly, for every program and input, whether the program will get stuck in an infinite loop. Real tools therefore work on restricted cases — spotting particular patterns, or analysing programs written in a restricted form — and report 'do not know' or give a wrong answer in the remaining cases. Any product claiming to detect all infinite loops in all programs is claiming something that cannot be done.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.