Imagine a student who tends to produce programs with infinite loops in them. Programs with infinite loops can be difficult to debug and challenging to grade. The student asks the following question: “Isn’t there an app that reads a Python program and determines whether the program has an infinite loop?” Unfortunately, no such program exists. Actually, we can prove mathematically that such a program cannot exist! If someone would sell such an app, it may detect infinite loops in a few programs, but it would not find infinite loops in all programs.
The Halting problem takes as input a program (written in any programming language) and it determines whether the program has an infinite loop. In 1936, Alan Turing proved that an algorithm to solve the Halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine. The Halting problem is an example of an undecidable problem.
Anyone reading material about unsolvable problems will encounter the terms decidable and undecidable. A problem that generates as output a “1” (YES) or “0” (NO) is called a decision problem. It only makes a decision. Decision problems are not particularly useful when writing programs, but they play a crucial role in the field of complexity theory (details are beyond the scope of the PD material). A decision problem is undecidable if there exists no algorithm for solving it. The Halting problem is an undecidable problem. The Wang tile problem is undecidable as discussed in the Wang tiles post.
For more information as well as historical background see:
- http://en.wikipedia.org/wiki/Halting_problem
- http://www.turing.org.uk/
- The site contains interesting links to descriptions of Alan Turing’s life. Your students may have seen the 2014 movie Imitation Game which focuses on Alan Turing’s work on breaking the Enigma code.
