Editing Turing completeness (section)

==Computability theory==
[[Computability theory]] uses [[Model of computation|models of computation]] to analyze problems and determine whether they are [[Computability|computable]] and under what circumstances. The first result of computability theory is that there exist problems for which it is impossible to predict what a (Turing-complete) system will do over an arbitrarily long time.

The classic example is the [[halting problem]]: create an algorithm that takes as input a program in some Turing-complete language and some data to be fed to ''that'' program, and determines whether the program, operating on the input, will eventually stop or will continue forever. It is trivial to create an algorithm that can do this for ''some'' inputs, but impossible to do this in general. For any characteristic of the program's eventual output, it is impossible to determine whether this characteristic will hold.

This impossibility poses problems when analyzing real-world computer programs. For example, one cannot write a tool that entirely protects programmers from writing infinite loops or protects users from supplying input that would cause infinite loops.

One can instead limit a program to executing only for a fixed period of time ([[Timeout (computing)|timeout]]) or limit the power of flow-control instructions (for example, providing only loops that iterate over the items of an existing array). However, another theorem shows that there are problems solvable by Turing-complete languages that cannot be solved by any language with only finite looping abilities (i.e., languages that guarantee that every program will eventually finish to a halt). So any such language is not Turing-complete. For example, a language in which programs are guaranteed to complete and halt cannot compute the computable function produced by [[Cantor's diagonal argument]] on all computable functions in that language.