Universal Turing Machine

Universal Turing Machines (UTM) were first described by Alan Turing in 1936. One definition, taken from the Wikipedia, states:

“... a Turing machine consists of:

• A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol.
• A head that can read and write symbols on the tape and move left and right one (and only one) step at a time.
• A state register that stores the state of the Turing machine. The number of different states is always finite and there is one special start state with which the state register is initialized.
• An action table (or transition function) that tells the machine what symbol to write, how to move the head ('L' for one step left, and 'R' for one step right) and what its new state will be, given the symbol it has just read on the tape and the state it is currently in. If there is no entry in the table for the current combination of symbol and state then the machine will halt.“

The UTM implemented in the example can also be found on that wikipedia page and is reprinted here:

“The following Turing machine has an alphabet {‘0‘, ‘1‘}, with 0 being the blank symbol. It expects a series of 1s on the tape, with the head initially on the leftmost 1, and doubles the 1s with a 0 in between, i.e., “111“ becomes “1110111“. The set of states is {s1, s2, s3, s4, s5} and the start state is s1. The action table is as follows.

A computation of this Turing machine might for example be: (the position of the head is indicated by displaying the cell in bold face)