Turing Complete

From CryptoCurrency Wiki

Revision as of 13:33, 6 June 2022 by Oscarius (talk | contribs) (1 revision imported)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

"A computer is Turing complete if it can solve any problem that a Turing machine can, given an appropriate algorithmand the necessary time and memory. When applied to a programming language, this phrase means that it can fully exploit the capabilities of a Turing complete computer.

Actual computers have to operate on limited memory and are not Turing complete in the mathematical sense. If they can run any program they are equivalent to linear bounded automata, a weaker theoretical machine. Informally, however, calling a computer Turing complete means that it can execute any algorithm.

The ability to run any algorithm is a necessary condition for a computer to be called Turing complete. For this reason, a basic calculator is not Turing complete and neither is a scientific calculator that only evaluates specific functions."