Computability Theory
The first result of computability theory is that it is impossible in general to predict what a Turing-complete program will do over an arbitrarily long time. For example, it is impossible to determine for every program-input pair whether the program, operating on the input, will eventually stop or will continue forever (see halting problem). It is impossible to determine whether the program will return "true" or whether it will return "false". For any characteristic of the program's eventual output, it is impossible to determine whether this characteristic will hold. This can cause problems in practice when analyzing real-world computer programs. One way to avoid this is to cause programs to stop executing after a fixed period of time, or to limit the power of flow control instructions. Such systems are not Turing complete by design.
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., any language that guarantees every program will eventually finish to a halt). Given a guaranteed halting language, the computable function which is produced by Cantor's diagonal argument on all computable functions in that language is not computable in that language.
Read more about this topic: Turing Completeness
Famous quotes containing the word theory:
“Freud was a hero. He descended to the “Underworld” and met there stark terrors. He carried with him his theory as a Medusa’s head which turned these terrors to stone.”
—R.D. (Ronald David)