\newpage\section {Universal Algorithm; Diagonal Results.} \label{diagonal}
\subsection {Universal Turing Machine.}
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
$f\in R$ in time $c^2 T$ and space $S+c$, where $S,T$ are space
and time of computing $f(x)$ 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 $u(m x)$
operates in cycles. Each cycle simulates one step of $M(x)$. Let
after $i$ steps of $M(x)$, $l_i$ be the left (from the head) part
of its tape; $r_i$ be the rest of the tape and $s_i$ be the head's
state. The tape configuration of $u(m x)$ after $i$ cycles is
$t_i=l_i m s_i r_i$. Then $u$ looks up $m$ to find the command
corresponding to the state $s_i$ and the first character of $r_i$
and modifies $t_i$ accordingly. When $M(x)$ halts, $u(m x)$ erases
the (penciled) $s_i$ from the tape and halts too. Universal
Multi-head TM works similarly but can also determine in time
$O(t(x))$ whether it halts in $t$ steps (given $x,t(x)$ and an
appropriate program).
\paragraph {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 under cs332 at \href {https://www.cs.bu.edu/teaching/}
{https://www.cs.bu.edu/teaching/}).
\noindent\parbox {24pc} {\hspace*{1pc} The transition table at the right
defines a small (11 states + 6 symbols) TM $U$ by Ikeno which can simulate any
other TM $M$ over $\{0,1\}$ tape alphabet with the following stipulations
(which still allow $M$ to simulate any other TMs): The direction of head shift
is a function of the new post-transition state (lower case - left, upper case
- right). And so is, for $M$ only, the digit typed. The tape is infinite to the
right only: the left states in the leftmost cell remain there. For $M$ only,
the new state is the tape bit read plus a function of the old state. In the $U$
table the states and tape digits are shown only when changed; except that the
prime is always shown. The external choice, halt, etc. commands are special
states for $M$; for $U$ they are shown as A/B or =.} \hfill\({\begin{tabular}
{|c||c|c|c|c|c|c|}\hline %---------------------------------+
& 1' & 0' & *' & 1 & 0 & * \\ % | 1' | 0' | *' | 1 | 0 | * |
\hline\hline %---+-----------------------------|
A & & & & f & f & e0\\ % A | | | | f | f | e0 |
B & & & & F & F & e1\\ % B | | | | F | F | e1 |
\hline %---|----+----+----+----+----+----|
f,F& & & c & b* & a*& F \\ %f,F| | | c | b* | a* | F |
\hline %---|----+----+----+----+----+----|
c & = & F & E' & ' & ' & \\ % c | = | F | E' | ' | ' | |
a & b' & F & E' & ' & ' & ' \\ % a | b' | F | E' | ' | ' | ' |
\hline % |----+----+----+----+----+----|
b & & a' & D & ' & ' & ' \\ % b | | a' | D | ' | ' | ' |
d & ' & ' & D & ' & ' & \\ % d | ' | ' | D | ' | ' | |
\hline %---|----+----+----+----+----+----|
D & & & e' & d' & --& \\ % D | | | e' | d' | -- | |
E & ' & ' & e' & = & --& ' \\ % E | ' | ' | e' | = | -- | ' |
\hline %---|----+----+----+----+----+----|
e & B & A &A/B & ' & ' & ' \\ % e | B | A |A/B | ' | ' | ' |
\hline\end{tabular}}\) %---------------------------------+
$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 $F$. 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 $1^k$, if the next
state is $k$ segments to the left, or $0^k$ (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:
\mbox{$ *'0'0'0'1'0'*'0'0'0'0'01*011* ... *00\ \fbox{head}\ 00$}.
$U$ first reads the digit of an $M$'s cell changing the state from $F$
or $f$ to $a/b$, 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 $c/F$ or $d/D$) 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
$A/B$) 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!