Universality is the property of being able to perform different tasks with the same underlying construction just by being programmed in a different way. Universal systems are effectively capable of emulating any other system. Digital computers are universal, but proving that idealized computational systems are universal can be extremely difficult and technical. Nonetheless, examples have been found in many systems, and any system that can be translated into another system known to be universal must itself be universal. Specific universal Turing machines, universal cellular automata (in both one and two dimensions), and universal cyclic tag systems are known, although the smallest universal example is known only in the case of elementary cellular automata (Wolfram 2002, Cook 2004).

See also

Game of Life, Principle of Computational Equivalence, Rule 110, Universal Cellular Automaton, Universal Turing Machine, Universality Class

Explore with Wolfram|Alpha


Cook, M. "Universality in Elementary Cellular Automata." Complex Systems 15, 1-40, 2004.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 642-644, 2002.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "Universality." From MathWorld--A Wolfram Web Resource.

Subject classifications