4,781
edits
Changes
Jump to navigation
Jump to search
famous theoretical computer science problem
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 undecideable. 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]]
[[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is undecideable. 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]]