Editing Computability (section)

==== The halting problem ====
{{Main|Halting problem}}

The halting problem is one of the most famous problems in computer science, because it has profound implications on the theory of computability and on how we use computers in everyday practice.  The problem can be phrased:

: ''Given a description of a Turing machine and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.''

Here we are asking not a simple question about a prime number or a palindrome, but we are instead turning the tables and asking a Turing machine to answer a question about another Turing machine.  It can be shown (See main article: [[Halting problem]]) that it is not possible to construct a Turing machine that can answer this question in all cases.

That is, the only general way to know for sure if a given program will halt on a particular input in all cases is simply to run it and see if it halts.  If it does halt, then you know it halts.  If it doesn't halt, however, you may never know if it will eventually halt.  The language consisting of all Turing machine descriptions paired with all possible input streams on which those Turing machines will eventually halt, is not recursive.  The halting problem is therefore called non-computable or '''[[undecidable problem|undecidable]]'''.

An extension of the halting problem is called [[Rice's theorem]], which states that it is undecidable (in general) whether a given language possesses any specific nontrivial property.