\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!