Friday, March 13, 2015

The Halting Problem

This is a great video that describes the halting problem.


https://www.youtube.com/watch?v=92WHN-pAFCs


What is the halting problem you ask?
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.

http://en.wikipedia.org/wiki/Halting_problem


No comments:

Post a Comment