Impossible Programs
Impossible Programs is the name of a lecture by Tom Stuart.
It concerns computer programs which are impossible -- that is, paradoxical.
Such programs demonstrate the Halting problem and other interesting features.
Contents
Four kinds of problems
Stuart observes that we use computer programs to solve problems, and that problems fall into four broad categories:
- Vague
- Difficult
- Expensive
- Impossible
Impossible problems, impossible programs
The lecture concerns impossible problems. Impossible problems have no solutions: solutions are impossible.
It is not possible to create computer programs which solve impossible problems.
Computer programs which attempt to solve impossible problems are impossible programs.
An impossible program exists: it is a computer program, a set of symbols in a programming language.
But an impossible program does not do what programs are supposed to do.
Impossible programs do not compute, or cannot be trusted to compute.
Conclusions
Not only can we not ask "does this program halt?", we also can't ask "does this program do what I want it to do?"
See also
External links
- Impossible Programs lecture video
- Impossible Programs: a great lecture on some of computer science's most important subjects @ BoingBoing
