There are some Turing machines that can simulate all other Turing machines; these are called *universal*. This works as follows. Suppose Turing machine (TM) A is universal, and we want to simulate another TM, which we'll call B. So we'll encode a description of B and its tape onto the tape of A. Then, A will read that encoded description and simulate the actions of B, halting when B halts. The "encoded description" is essentially a program; the universal machine is a primitive version of a *stored-program computer*. The existence of universal machines is convenient, because it means that we don't have to build a new machine for each task; a universal machine suffices for all tasks. ## Building the machine Here's how I've encoded the example program from [[Simulating Turing machines]], which squares a unary number. If you open that page and compare the two, it's pretty easy to see the parallels. Each state starts with `B0`; the active state is marked `B1`. Each rule starts with `C0`, and contains the same four pieces of information encoded in unary: the symbol under the head, the symbol to replace it with, the new state, and the direction to move. (The ordering is slightly different from the original code). Directions are encoded as either `1` (left), `1 1` (right), or `1 1 1` (none). The definition of the machine is preceded and followed by an `A0`, and immediately afterwards is an encoded version of the initial tape of the simulated machine, with the current cell marked by `B1` and the rest marked by `B0`. ``` A0 B1 C0 1 1 1 1 D0 1 1 1 1 D0 1 D0 1 1 C0 1 1 1 1 1 D0 1 1 1 1 1 D0 1 D0 1 1 C0 1 1 1 1 1 1 1 D0 1 1 1 1 1 1 1 D0 1 D0 1 1 C0 1 1 1 D0 1 1 1 1 1 D0 1 1 D0 1 1 1 C0 1 1 1 1 1 1 D0 1 1 1 1 1 1 1 D0 1 1 D0 1 1 1 C0 1 1 D0 1 1 D0 1 1 1 1 D0 1 B0 C0 1 1 1 1 1 D0 1 1 1 1 1 D0 1 1 D0 1 C0 1 1 1 1 D0 1 1 1 1 D0 1 1 D0 1 C0 1 1 1 D0 1 1 1 D0 1 1 D0 1 C0 1 1 1 1 1 1 1 D0 1 1 1 1 1 1 1 D0 1 1 D0 1 C0 1 D0 1 1 1 D0 1 1 1 D0 1 1 B0 C0 1 1 1 D0 1 1 1 D0 1 1 1 D0 1 1 C0 1 1 1 1 D0 1 1 1 1 D0 1 D0 1 1 1 B0 C0 1 1 1 1 1 1 1 D0 1 1 1 1 1 1 D0 1 1 1 1 D0 1 C0 1 1 1 1 1 D0 1 1 1 1 1 1 D0 1 1 1 1 1 1 D0 1 B0 C0 1 1 1 1 1 D0 1 1 1 D0 1 1 1 1 1 D0 1 C0 1 1 1 1 D0 1 1 1 1 D0 1 D0 1 1 1 B0 C0 1 1 1 1 1 D0 1 1 1 1 1 D0 1 1 1 1 1 D0 1 1 1 C0 1 1 1 1 D0 1 1 1 1 D0 1 1 1 1 1 1 1 D0 1 1 1 B0 A0 B1 1 1 1 1 B0 1 1 1 B0 1 1 1 B0 1 1 1 B0 1 1 ``` Here's a high-level overview of how the universal machine works (code is [here](https://github.com/sidmani/turing/blob/master/examples/universal.tm)). 1. Find the current state (marked by `B1`), and mark the first rule by replacing `C0` with `C1`. Try to match the left-hand symbol with the symbol in the current cell on the tape. If this fails, reset this rule's `C1` to `C0`, mark the next rule, and try again. 2. Once one of the rules has matched, replace the symbol at the current cell with the new symbol. Since the symbols may not be the same length, shift the tape left or right as necessary. 3. Move the head of the machine by resetting the `B1` on the current tape cell to `B0`, and marking the cell to the left or right with `B1` as specified. If we are on the edge of the tape, add a new cell with the empty character (`1`). If this is the left edge, that requires shifting the whole tape right. 4. Change the current state to the new one specified by index in the matched rule. This involves resetting `B1` to `B0` and counting up to the nth `B0` in the machine definition. 5. If the state has no rules, halt. Otherwise, go to step 1. This sounds simple, but since Turing machines don't have addressable memories it requires moving back and forth over the tape repeatedly for even simple operations like comparing symbols. The original Turing machine takes 57 steps to compute $2^2 = 4$. The universal machine takes 491620. That said, my machine, which has 65 states and 11 symbols, is not even close to the simplest universal machine known; [Wolfram devised a universal machine with 2 states and 3 symbols](https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine). The tradeoff is that the procedure for encoding a machine onto the tape would likely become vastly more complex.