A property of a computational system indicating it can simulate any general-purpose programmable machine and thus perform any computation that such an ideal machine can, given unbounded time and memory.

Principle

Universality by simulation: if a system can emulate the state transitions of an ideal programmable machine, it attains the same class of computable behaviors under idealized resources.

Demonstration

A minimal imperative language with conditional branching and unbounded integer storage can simulate a universal machine and is therefore Turing-complete; cellular automaton Rule 110 is a standard constructive example.

Misapplication

Equating Turing completeness with practical usability, efficiency, decidability, or guaranteed termination is incorrect; completeness only concerns representational universality under idealized resources.

Consequence

When a system is Turing-complete, one can encode any algorithmic procedure in it, but classical undecidability and nontermination results then also apply to programs written in that system.

Reversal

A Turing-incomplete system lacks the ability to simulate arbitrary universal computations and therefore cannot express every algorithmic process, though it may be decidable or more predictable.

Boundary

Depends on idealizations such as unbounded memory and precise control of state; models with finite memory, restricted control flow, or nonprogrammable primitives fall outside this property.

Semantic Tension

Differs from informal notions of expressiveness or convenience: a language can be expressive for users without being Turing-complete, and vice versa; completeness is a formal simulation property, not a usability metric.

Synthesis

Turing completeness classifies systems by their capacity to emulate a universal programmable machine under ideal resources, implying both maximal representational power and the inheritance of undecidability phenomena.