Editing Turing completeness (section)

==Formal definitions==
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 machine]]s. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known physically-implementable Turing-complete systems are Turing-equivalent, which adds support to the [[Church–Turing thesis]].{{Citation needed|date=March 2021}})
;(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 input streams with infinitely many 1s.