Difference between revisions of "Impossible Programs"
Karl Jones (Talk | contribs) (→Four kinds of problems) |
Karl Jones (Talk | contribs) (→External links) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 3: | Line 3: | ||
It concerns [[Computer program|computer programs]] which are ''impossible'' -- that is, [[Paradox|paradoxical]]. | It concerns [[Computer program|computer programs]] which are ''impossible'' -- that is, [[Paradox|paradoxical]]. | ||
| − | Such programs demonstrate the [[Halting problem]] | + | Such programs demonstrate the [[Halting problem]]; see also [[Gödel's incompleteness theorems]]. |
== Four kinds of problems == | == Four kinds of problems == | ||
| Line 34: | Line 34: | ||
== See also == | == See also == | ||
| + | * [[Computer program]] | ||
| + | * [[Computer programming]] | ||
| + | * [[Gödel's incompleteness theorems]] | ||
| + | * [[Halting problem]] | ||
* [[Paradox]] | * [[Paradox]] | ||
| Line 40: | Line 44: | ||
* [https://vimeo.com/66849976 Impossible Programs] lecture video | * [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 | * [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:Computer programs]] | ||
| + | [[Category:Logic]] | ||
| + | [[Category:Mathematics]] | ||
| + | [[Category:Paradox]] | ||
Latest revision as of 13:08, 24 April 2016
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.
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
