Turingcomplete

Turing completeness is a property of a system of rules or a programming language that can simulate any Turing machine, given sufficient time and memory. A Turing machine is a theoretical device that manipulates symbols on an infinite tape according to a finite set of rules. A system is said to be Turing complete if it can perform any computation that a Turing machine can, given unbounded resources.

In practice, unbounded memory and time are theoretical ideals; real hardware imposes limits. Turing completeness is about expressive power and general computability, not speed or practicality.

Examples include most general-purpose programming languages such as C, Java, Python, and Lisp, which are routinely used to implement arbitrary algorithms. Esoteric languages like Brainfuck claim Turing completeness for the same reason. Non-trivial cellular automata, notably Conway's Game of Life, can also simulate a Turing machine and are therefore Turing complete.

Some systems deliberately omit Turing completeness by constraining features or resources—for example, finite-state machines or many simple regular expression engines—limiting their computational capabilities.

The concept is closely related to the Church-Turing thesis, which posits that any function that is effectively computable can be computed by a Turing machine; thus, Turing-complete languages are, in principle, capable of expressing any computable function.