Explore Wolfram's Turing machines from "A New Kind of Science"
Universal computation with simple rules: head states, tape symbols, and transition rules
Turing machines, extensively studied by Stephen Wolfram in "A New Kind of Science," are fundamental models of computation consisting of a tape of cells, a head that can read and write symbols, and a finite set of states. The machine follows transition rules that determine what symbol to write, which direction to move, and what new state to enter based on the current state and symbol.
Wolfram demonstrated that even very simple Turing machines can exhibit complex behavior and achieve universal computation. His famous 2-state 3-symbol machine was proven universal in 2007, making it the smallest known universal Turing machine. This supports his Principle of Computational Equivalence - that complex computation is ubiquitous in simple systems.