Turing completeness

Computer/Terms 2008. 4. 29. 09:08

In computability theory, several closely-related terms are used to describe the "computational power" of a computational system (such as an abstract machine or programming language):

Turing completeness — A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a universal Turing machine.
Turing equivalence — A Turing-complete system is called Turing-equivalent if every function it can compute is also Turing-computable; i.e., it computes precisely the same class of functions as do Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing-equivalent, which adds support to the Church-Turing thesis.)
(Computational) universality — A system is called universal with respect to a class of systems if it can compute every function computable by systems in that class (or can simulate each of those systems). Typically, universality is tacitly with respect to a Turing-complete class of systems. The term weakly universal is sometimes used to distinguish a system (e.g. a cellular automaton) whose universality is achieved only by modifying the standard definition of Turing machine so as to include unbounded input.

Reference:
http://en.wikipedia.org/wiki/Turing_complete

Posted by 알 수 없는 사용자
,