Example of Completeness

1 ANSWERS

1. Ali Abdullah
   

   Hi, 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, the term universality is tacitly used 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.

   Report (0) (0)  |   2 years, 7 month(s) ago