Turing Complete

From CryptoWiki

Revision as of 09:31, 21 August 2020 by wiki_crypto>Zeb.dyor
(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."