View source for Impossible Programs

'''''Impossible Programs''''' is the name of a lecture by [[Tom Stuart]].

It concerns [[Computer program|computer programs]] which are ''impossible'' -- that is, [[Paradox|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 [[Problem solving|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 == 

* [https://vimeo.com/66849976 Impossible Programs] lecture video
* [http://boingboing.net/2013/05/28/impossible-programs-a-great-l.html Impossible Programs: a great lecture on some of computer science's most important subjects] @ BoingBoing

[[Category:Logic]]
[[Category:Mathematics]]
[[Category:Paradox]]