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; see also Gödel's incompleteness theorems.

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

• Computer program
• Computer programming
• Gödel's incompleteness theorems
• Halting problem
• Paradox

External links

• Impossible Programs lecture video
• Impossible Programs: a great lecture on some of computer science's most important subjects @ BoingBoing