Difference between revisions of "Impossible Programs"

From Wiki @ Karl Jones dot com
Jump to: navigation, search
(etc)
(http://boingboing.net/2013/05/28/impossible-programs-a-great-l.html)
Line 31: Line 31:
  
 
* [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

Revision as of 10:49, 19 August 2015

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.

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

The lecture concerns impossible problems.

It is not possible for computer programs to solve these problems.

Because the problem is impossible, it is impossible for computer programs to solve the problem.

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