2 ms·
Wolfram's 2-state 3-symbol Turing machine
- peter_d_sherman 6y agoThink of this as a computer comprising only a single 1-bit register, no stack, and memory locations that can only be in one of three states, that is, 0, 1 or 2... (they could be 2-bit values -- where the number 3, the fourth combination of bits, is prohibited...) There are only six possible instructions, based on the combination of the value in the memory location, and the value of the single 1-bit register... This computer is capable of computing anything that any other computer can, because it's Turing-complete (albeit at a much slower speed)... This might be the absolute minimum architecture that a computer can be created with...