The first computers were hardware-programmable. To change the function computed, one had to reconnect the wires or even build a new computer. John von Neumann suggested using Turing's Universal Algorithm. The function computed can be then specified by just giving its description (program) as part of the input rather than by changing the hardware. This was a radical idea, since in the classical mathematics universal functions do not exist (as we will see).
Let R be the class of all TM-computable total (defined for all
inputs) and partial (which may diverge) functions. Surprisingly, there
is a universal function u in R. It simulates any other
in time 
and space S+c, where S,T> |x|
are space and time of computing 
and c is its program length. This u
expects the prefix m of its input m x to list the commands
of a Turing Machine M and its initial head state. Then 
operates in cycles. Each cycle
simulates one step of 
. Let
after i steps of 
, 
be the left (from the head) part of
its tape; 
be the rest of the
tape and 
be the head's state.
The tape configuration of 
after i cycles is 
. Then
u looks up m to find the command corresponding to the
state 
and the first character
of 
and modifies 
accordingly. When 
halts, 
erases 
from the tape and halts
too. Universal Multi-head TM works similarly but can also determine in
time 
whether it halts in
t steps (given 
and an
appropriate program).
Problem. Design a universal multi-head TM with a constant factor overhead. Hint: When heads split or merge in the first cell, the room u needs for their programs creates sparse or dense info regions that propagate right (sparse faster).
We now describe in detail a simpler but slower universal TM (see also its simulator (click cs332)).
U's tape consist of segments: each is a 0/1
string preceded with a *. Some symbols are primed. Each finite segment
describes a transition performed by one state of M and never
changes (except for primes). The rightmost (infinite) segment is always
a copy of M's tape, initially with U's head at the same
location in the state C. Each transition is represented as
STW, where W is the symbol to write, T the
direction L/R to turn, represented as 0/1, S the new state (when
0 is read). S is represented as 
, if the next state is k segments to the left, or
(if to the right). Initially,
primed are the digits of S in the segment corresponding to the
initial state of M and all digits to their left. An example of
the configuration: 
.
U first reads the digit of an M's cell changing the
state from C or f to 
, puts a * there, moves left to the primed state segment
S, finds from it the new state segment and moves there. With only
10 head states, U can't find the new segment at once. So, it
(alternating the states 
or
) keeps priming nearest
unprimed * and 1s of S (or unpriming 0s). When S is
exhausted the target segment, |S| stars away, is reached. Then
U reads (changing state from e to 
) the rightmost symbol W of the new segment,
copies it at the * in the M area, goes back, reads the next
symbol T returns to the just overwritten (and first unprimed)
cell of M area and turns left or right. As CA, M and
U have in each cell three standard bits: present and previous
pointer directions and a ``content'' bit to store M's symbol. In
addition U needs just 3 states of its own!