Difference between revisions of "Impossible Programs"

From Wiki @ Karl Jones dot com
Jump to: navigation, search
(etc)
(etc)
Line 12: Line 12:
 
* Impossible
 
* Impossible
  
The lecture concerns impossible problems.
+
The lecture concerns impossible problems.
 +
 
 +
It is not possible for computer programs to solve these problems.  The programs themselves are impossible.
 +
 
 +
Impossible programs demonstrate the [[Halting 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 ==
 
== See also ==

Revision as of 08:36, 19 August 2015

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

It concerns computer programs which are paradoxical.

Stuart observes that we use computer programs to solve problems, and that problems fall into four broad categories.

Four kinds of problems

  • Vague
  • Difficult
  • Expensive
  • Impossible

The lecture concerns impossible problems.

It is not possible for computer programs to solve these problems. The programs themselves are impossible.

Impossible programs demonstrate the Halting 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