Turing completeness
From ScienceZero
Revision as of 21:47, 2 September 2007 by Bjoern (Talk | contribs) (New page: A machine or programming language is called Turing complete, Turing equivalent, or (computationally) universal if it has a computational power equivalent to (i.e., capable of emulating) a ...)
A machine or programming language is called Turing complete, Turing equivalent, or (computationally) universal if it has a computational power equivalent to (i.e., capable of emulating) a mathematical model of a programmable computer known as the universal Turing machine. Being Turing equivalent means being able to perform any computational task without any regards to memory or time requirements.
The term derives from the name of mathematician Alan Turing who introduced the model of the universal Turing machine in 1936.
