Difference between revisions of "Halting problem"
m (link) |
m (spelling: undecideabe -> undecidabe) |
||
| Line 1: | Line 1: | ||
The '''Halting Problem''' is a problem in theoretical [[computer science]] which measures the effectiveness with which [[computer]]s execute [[algorithm]]s. In the theoretical formulation, computers are represented by [[Turing machine]]s and algorithms are represented by an infinitely long piece of tape that moves around inside the Turing machine. The tape has instructions for the machine; if it can execute this instruction it moves to the next piece of tape, if it cannot, the machine halts. The Halting Problem asks for a reliable prediction of whether a particular machine will halt before you put the tape into it. | The '''Halting Problem''' is a problem in theoretical [[computer science]] which measures the effectiveness with which [[computer]]s execute [[algorithm]]s. In the theoretical formulation, computers are represented by [[Turing machine]]s and algorithms are represented by an infinitely long piece of tape that moves around inside the Turing machine. The tape has instructions for the machine; if it can execute this instruction it moves to the next piece of tape, if it cannot, the machine halts. The Halting Problem asks for a reliable prediction of whether a particular machine will halt before you put the tape into it. | ||
| − | [[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is [[ | + | [[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is [[undecidable]]. In other words, one can never truly rely on a computer to halt its computations. While this is theoretically significant, in practice most computer programs have been written so that they do not have [[runtime error]]s. |
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
Revision as of 03:03, September 16, 2008
The Halting Problem is a problem in theoretical computer science which measures the effectiveness with which computers execute algorithms. In the theoretical formulation, computers are represented by Turing machines and algorithms are represented by an infinitely long piece of tape that moves around inside the Turing machine. The tape has instructions for the machine; if it can execute this instruction it moves to the next piece of tape, if it cannot, the machine halts. The Halting Problem asks for a reliable prediction of whether a particular machine will halt before you put the tape into it.
Alan Turing, the founding father of theoretical computer science, showed the Halting Problem is undecidable. In other words, one can never truly rely on a computer to halt its computations. While this is theoretically significant, in practice most computer programs have been written so that they do not have runtime errors.
