Models of Computation

Lecture 8: Universal Models [Fa’14]

Caveat lector: This note is not even a first draft, but more of a rough sketch, with many
topics still to be written and/or unwritten. But the semester is over, so it’s time to put it down.
Please send bug reports and suggestions to jeffe@illinois.edu.
Any sufficiently advanced technology is indistinguishable from magic.
— Arthur C. Clarke, “Hazards of Prophecy: The Failure of Imagination” (1962)
Any technology that is distinguishable from magic is insufficiently advanced.
— Barry Gehm, quoted by Stan Schmidt in ANALOG magazine (1991)

8ÆÆÆ

Universal Models of Computation
Remind about the Church-Turing thesis.
There is some confusion here between universal models of computation and thesomewhat wider class of undecidable problems/languages.

8.1

Universal Turing Machines

The pinnacle of Turing machine constructions is the universal Turing machine. For modern
computer scientists, it’s useful to think of a universal Turing machine as a "Turing machineinterpreter written in Turing machine". Just as the input to a Python interpreter is a string of
Python source code, the input to our universal Turing machine U is a string 〈M , w〉 that encodes
both an arbitrary Turing machine M and a string w in the input alphabet of M . Given theseencodings, U simulates the execution of M on input w; in particular,• U accepts 〈M , w〉 if and only if M accepts w.
• U rejects 〈M , w〉 if and only if M rejects w.
In the next few pages, I will sketch a universal Turing machine U that uses the input alphabet{0, 1, [, ], •, |} and a somewhat larger tape alphabet. However, I do not require that the Turingmachines that U simulates have similarly small alphabets, so we first need a method to encode
arbitrary input and tape alphabets.
Encodings
Let M = (Γ , , Σ, Q, start, accept, reject, δ) be an arbitrary Turing machine, with a single halfinfinite tape and a single read-write head. (I will consistently indicate the states and tape symbolsof M in slanted green to distinguish them from the upright red states and tape symbols of U.)
We encode each symbol a ∈ Γ as a unique string |a| of dlg(|Γ |)e bits. Thus, if Γ = {0, 1, $, x, },
we might use the following encoding:〈0〉 = 001,〈1〉 = 010,〈$〉 = 011,〈x〉 = 100,〈〉 = 000.

The input string w is encoded by its sequence of symbol encodings, with separators • between
every pair of symbols and with brackets [ and ] around the whole string. For example, with thisencoding, the input string 001100 would be encoded on the input tape as〈001100〉 = [001•001•010•010•001•001]© Copyright 2017 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/ for the most recent revision.

1Models of Computation

Lecture 8: Universal Models [Fa’14]

Similarly, we encode each state q ∈ Q as a distinct string 〈q〉 of dlg|Q|e bits. Without loss ofgenerality, we encode the start state with all 1s and the reject state with all 0s. For example, if
Q = {start, seek1, seek0, reset, verify, accept, reject}, we might use the following encoding:〈start〉 = 111〈seek1〉 = 010〈seek0〉 = 011〈verify〉 = 101〈accept〉 = 110〈reject〉 = 000〈reset〉 = 100

We encode the machine M itself as the string 〈M 〉 = [〈reject〉•〈〉]〈δ〉, where 〈δ〉 is theconcatenation of substrings [〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] encoding each transition δ(p, a) = (q, b, ∆)such that q 6= reject. We encode the actions ∆ = ±1 by defining 〈−1〉 := 0 and 〈+1〉 := 1.
Conveniently, every transition string has exactly the same length. For example, with the symboland state encodings described above, the transition δ(reset, $) = (start, $, +1) would be encodedas[100•011|001•011•1].
Our first example Turing machine for recognizing {0n 1n 0n | n ≥ 0} would be represented by
the following string (here broken into multiple lines for readability):[000•000][[001•001|010•011•1][001•100|101•011•1][010•001|010•001•1][010•100|010•100•1][010•010|011•100•1][011•010|011•010•1][011•100|011•100•1][011•001|100•100•1][100•001|100•001•0][100•010|100•010•0][100•100|100•100•0][100•011|001•011•1][101•100|101•011•1][101•000|110•000•0]]
Finally, we encode any configuration of M on U’s work tape by alternating between encodingsof states and encodings of tape symbols. Thus, each tape cell is represented by the string[〈q〉•〈a〉] indicating that (1) the cell contains symbol a; (2) if q 6= reject, then M ’s head islocated at this cell, and M is in state q; and (3) if q = reject, then M ’s head is located somewhere
else. Conveniently, each cell encoding uses exactly the same number of bits. We also surroundthe entire tape encoding with brackets [ and ].
For example, with the encodings described above, the initial configuration (start, 001100, 0)
Î
for our first example Turing machine would be encoded on U’s tape as follows.
〈start, 001100, 0〉 = [[111•001][000•001][000•010][000•010][000•001][000•001]]
Î
|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}
start 0reject 0

reject 1

reject 1

reject 0

reject 0

Similarly, the intermediate configuration (reset, $0x1x0, 3) would be encoded as follows:Î〈reset, $$x1x0, 3〉 = [[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}|
{z
}
reject $reject 0

reject x

reset 1

reject x

reject 0

Input and Execution
Without loss of generality, we assume that the input to our universal Turing machine U is given
on a separate read-only input tape, as the encoding of an arbitrary Turing machine M followedby an encoding of its input string x. Notice the substrings [[ and ]] each appear only only once
on the input tape, immediately before and after the encoded transition table, respectively. U also
has a read-write work tape, which is initially blank.
2Models of Computation

Lecture 8: Universal Models [Fa’14]

We start by initializing the work tape with the encoding 〈start, x, 0〉 of the initial configurationof M with input x. First, we write [[〈start〉•. Then we copy the encoded input string 〈x〉 onto
the work tape, but we change the punctuation as follows:• Instead of copying the left bracket [, write [[〈start〉•.
• Instead of copying each separator •, write ][〈reject〉•• Instead of copying the right bracket ], write two right brackets ]].
The state encodings 〈start〉 and 〈reject〉 can be copied directly from the beginning of 〈M 〉(replacing 0s for 1s for 〈start〉). Finally, we move the head back to the start of U’s tape.
At the start of each step of the simulation, U’s head is located at the start of the work tape.
We scan through the work tape to the unique encoded cell [〈p〉•〈a〉] such that p 6= reject.
Then we scan through the encoded transition function 〈δ〉 to find the unique encoded tuple[〈p〉•〈a〉|〈q〉•〈b〉•〈∆〉] whose left half matches our the encoded tape cell. If there is no suchtuple, then U immediately halts and rejects. Otherwise, we copy the right half 〈q〉•〈b〉 of thetuple to the work tape. Now if q = accept, then U immediately halts and accepts. (We don’t
bother to encode reject transformations, so we know that q 6= reject.) Otherwise, we transfer
the state encoding to either the next or previous encoded cell, as indicated by M ’s transition
function, and then continue with the next step of the simulation.
During the final state-copying phase, we ever read two right brackets ]], indicating that
we have reached the right end of the tape encoding, we replace the second right bracket with[〈reject〉•〈〉]] (mostly copied from the beginning of the machine encoding 〈M 〉) and thenscan back to the left bracket we just wrote. This trick allows our universal machine to pretendthat its tape contains an infinite sequence of encoded blanks [〈reject〉•〈〉] instead of actual
blanks .
ExampleAs an illustrative example, suppose U is simulating our first example Turing machine M on
the input string 001100. The execution of M on input w eventually reaches the configuration(seek1, $$x1x0, 3). At the start of the corresponding step in U’s simulation, U is in the followingÎ
configuration:[[000•011][000•011][000•100][010•010][000•100][000•001]]
ÎFirst U scans for the first encoded tape cell whose state is not reject. That is, U repeatedly
compares the first half of each encoded state cell on the work tape with the prefix [〈reject〉• of
the machine encoding 〈M 〉 on the input tape. U finds a match in the fourth encoded cell.

[[000•011][000•011][000•100][010•010][000•100][000•001]]
Î
Next, U scans the machine encoding 〈M 〉 for the substring [010•010 matching the current encoded cell. U eventually finds a match in the left size of the the encoded transition[010•010|011•100•1]. U copies the state-symbol pair 011•100 from the right half of thisencoded transition into the current encoded cell. (The underline indicates which symbols arechanged.)[[000•011][000•011][000•100][011•100][000•100][000•001]]
Î3

Models of Computation

Lecture 8: Universal Models [Fa’14]

The encoded transition instructs U to move the current state encoding one cell to the right. (Theunderline indicates which symbols are changed.)[[000•011][000•011][000•100][000•100][011•100][000•001]]
ÎFinally, U scans left until it reads two left brackets [[; this returns the head to the left end of
the work tape to start the next step in the simulation. U’s tape now holds the encoding of M ’s
configuration (seek0, $$xxx0, 4), as required.
Î

[[000•011][000•011][000•100][000•100][011•100][000•001]]
Î

8.2

Two-Stack Machines

A two-stack machine is a Turing machine with two tapes with the following restricted behavior.
At all times, on each tape, every cell to the right of the head is blank, and every cell at or to theleft of the head is non-blank. Thus, a head can only move right by writing a non-blank symbol
into a blank cell; symmetrically, a head can only move left by erasing the rightmost non-blankcell. Thus, each tape behaves like a stack. To avoid underflow, there is a special symbol at thestart of each tape that cannot be overwritten. Initially, one tape contains the input string, withthe head at its last symbol, and the other tape is empty (except for the start-of-tape symbol).

ÆÆÆ

Simulate a doubly-infinite tape with two stacks, one holding the tape contents to the left ofthe head, the other holding the tape contents to the right of the head. For each transitionof a standard Turing machine M , the stack machine pops the top symbol off the (say) left
stack, changes its internal state according to the transition δ, and then either pushes a new
symbol onto the right stack, or pushes a new symbol onto the left stack and then moves the
top symbol from the right stack to the left stack.

8.3

ÆÆÆ

Counter Machines
A configuration of a k-counter machine consists of k non-negative integers and an internal
state from some finite set Q. The transition function δ : Q × {0, +1}k → Q × {−1, 0, +1}k takes
an internal state and the signs of the counters as input, and produces a new internal state andchanges to counters as output.
• Prove that any Turing machine can be simulated by a three-counter machine. One
counter holds the binary representation of the tape after the head; another counterholds the reversed binary representation of the tape before the head. Implementtransitions via halving, doubling, and parity, using the third counter for scratch work.
• Prove that two counters can simulate three. Store 2a 3 b 5c in one counter, use the otherfor scratch work.
• Prove that a three-counter machine can compute any computable function: Given input(n, 0, 0), we can compute ( f (n), 0, 0) for any computable function f . First transform(n, 0, 0) to (2n , 0, 0) using all three counters; then run two- (or three-)counter TM simulation to obtain (2 f (n) , 0, 0); and finally transform (2 f (n) , 0, 0) to ( f (n), 0, 0) using all
three counters.
• HARD: Prove that a two-counter machine cannot transform (n, 0) to (2n , 0). [Barzhdin
1963, Yao 1971, Schröpel 1972]4

Models of Computation

8.4

ÆÆÆ

Lecture 8: Universal Models [Fa’14]

FRACTRANFRACTRAN [Conway 1987]: A one-counter machine whose “program” is a sequence of rational
numbers. The counter is initially 1. At each iteration, multiply the counter by the first rational
number that yields an integer; if there is no such number, halt.
• Prove that for any computable function f : N → N, there is a FRACTRAN program thattransforms 2n+1 into 3 f (n)+1 , for all natural numbers n.
• Prove that every FRACTRAN program, given the integer 1 as input, either outputs 1 orloops forever. It follows that there is no FRACTRAN program for the increment function
n 7→ n + 1.

8.5

Post Correspondence Problem

Given n of pairs of strings (x 1 , y1 ), (x 2 , y2 ), . . . , (x n , yn ), is there a finite sequence of integers(i1 , i2 , . . . , ik ) such that x i1 x i2 · · · x ik = yi1 yi2 · · · yik ? For notation convenience, we write each pairxvertically as y instead of horizontally as (x, y). For example, given the string pairs
a=




 


0
01
110
, b=
, c=
,
100
00
11

we should answer True, because
 


110 01 110
0c bca =
11 00 11 100gives us 110110100 for both concatenations. As more extreme examples, the shortest solutions
for the input




 
0
001
1
a=
, b=
, c=
001
1
0
have length 75; one such solution is aacaaca b ba bccaaccaaaac baa b baac bac b bcc b bac bacc bc b
ac b bac bacc bac b b baccc ba b bcc baacaacaaac ba b baacac bcc b ba bac bcaacc baca b b b ba bcccc
bcaa ba baacc bc b b baccc ba b bcc b. The shortest solution for the instance




 


0
0
01
1111
a=
, b=
, c=
, d=
000
0101
1
10
is the unbelievable a2 b8 a4 c 16 a b4 a2 b4 ad 4 b3 c 8 a6 c 8 b2 c 4 bc 6 d 2 a18 d 2 c 4 d cad 2 c b54 c 3 d ca2 c 111 d c
a6 d 28 c b17 c 63 d 16 c 16 d 4 c 4 d c, which has total length 451. Finally, the shortest solution for the
instance






0
010
100
a=
, b=
, c=
,
00010
01
0
has length 528.

ÆÆÆThe simplest universality proof simulates a tag-Turing machine.

8.6

ÆÆÆ

Matrix Mortality
Given a set of integer matrices A1 , . . . , Ak , is the product of any sequence of these matrices(with repetition) equal to 0? Undecidable by reduction from PCP, even for two 15 × 15 matrices
or six 3 × 3 matrices [Cassaigne, Halava, Harju, Nicolas 2014]5

Models of Computation

8.7

Lecture 8: Universal Models [Fa’14]

Dynamical Systems

ÆÆÆ

Ray Tracing [Reif, Tygar, and Yoshida 1994] The configuration of a Turing machine is encoded
as the (x, y) coordinates of a light path crossing the unit square [0, 1] × [0, 1], where the x (resp. y -)coordinate encodes the tape contents to the left (resp. right) of the head. Needeither quadratic-surface mirrors or refraction to simulate transitions.
N-body problem [Smith 2006]: Similar idea
Skolem-Pisot reachability: Given an integer vector x and an integer matrix A, does An x =(0, . . . ) for any integer n? [Halava, Harju, Hirvensalo, Karhumäki 2005] It’s surprising that thisproblem is undecidable; the similar mortality problem for one matrix is not.

8.8

ÆÆÆ

Wang Tiles
Turing machine simulation is straightforward. Small Turing-complete tile sets via affine maps
(via two-stack machines) are a little harder.

8.9

Combinator Calculus

In the 1920s, Moses Schönfinkel developed what can now be interpreted as a model of computation
now called combinator calculus or combinatory logic. Combinator calculus operates on terms,
where every term is either one of a finite number of combinators (represented here by upper
case letters) or an ordered pair of terms. For notational convenience, we omit commas between
components of every pair and parentheses around the left term in every pair. Thus, SKK(IS) is
shorthand for the term (((S, K), K), (I, S)).
We can “evaluate” any term by a sequence of rewriting rules that depend on its first primitive
combinator. Schönfinkel defined three primitive combinators with the following evaluation rules:• Identity: I x 7→ x
• Constant: K x y 7→ x
• Substitution: S x yz 7→ xz( yz)Here, x, y, and z are variables representing unknown but arbitrary terms. “Computation” inthe combinator calculus is performed by repeatedly evaluating arbitrary (sub)terms with one ofthese three structures, until all such (sub)terms are gone.
For example, the term S(K(SI))K x y (for any terms x and y) evaluates as follows:

S(K(SI))Kx y 7→ K(SI) x(K x) y

Substitution

7→ SI(Kx) y

Constant

7→ Iy(K x y)

Substitution

7→ y(Kxy)

Identity

7→ y xConstantThus, we can define a new combinator R := S(K(SI))K that upon evaluation reverses the next
two terms: R x y 7→ y x.

6Models of Computation

Lecture 8: Universal Models [Fa’14]

On the other hand, evaluating SII(S(KI)(SII)) leads to an infinite loop:

SII(S(KI)(SII)) 7→ I(S(KI)(SII))(I(S(KI)(SII)))
7→ S(KI)(SII)(I(S(KI)(SII)))

Identity

7→ S(KI)(SII)(S(KI)(SII))

Identity

7→ KI(S(KI)(SII))(SII(S(KI)(SII)))ÆÆÆ

Substitution

Substitution

7→ I(SII(S(KI)(SII)))

Constant

7→ SII(S(KI)(SII))

Identity

Wikipedia sketches a direct undecidability proof. Is there a Turing-completeness proof thatavoids λ-calculus?

Exercises
1. A tag-Turing machine has two heads: one can only read, the other can only write. Initially,
the read head is located at the left end of the tape, and the write head is located at thefirst blank after the input string. At each transition, the read head can either move one cellto the right or stay put, but the write head must write a symbol to its current cell and move
one cell to the right. Neither head can ever move to the left.
Prove that any standard Turing machine can be simulated by a tag-Turing machine.
That is, given any standard Turing machine M , describe a tag-Turing machine M 0 that
accepts and rejects exactly the same input strings as M .
2. ? (a) Prove that any standard Turing machine can be simulated by a Turing machine with
only three states. [Hint: Use the tape to store an encoding of the state of the machine
yours is simulating.]Æ(b) Prove that any standard Turing machine can be simulated by a Turing machine with
only two states.

3. A two-dimensional Turing machine uses an infinite two-dimensional grid of cells as
the tape; at each transition, the head can move from its current cell to any of its
four neighbors on the grid. The transition function of such a machine has the form
δ : Q × Γ → Q × Γ × {↑, ←, ↓, →}, where the arrows indicate which direction the head should
move.
(a) Prove that any two-dimensional Turing machine can be simulated by a standard
Turing machine.
(b) Suppose further that we endow our two-dimensional Turing machine with thefollowing additional actions, in addition to moving the head:• Insert row: Move all symbols on or above the row containing the head up one
row, leaving the head’s row blank.
• Insert column: Move all symbols on or to the right of the column containing thehead one column to the right, leaving the head’s column blank.
• Delete row: Move all symbols above the row containing the head down one row,deleting the head’s row of symbols.
• Delete column: Move all symbols the right of the column containing the head
one column to the right, deleting the head’s column of symbols.
7Models of Computation

Lecture 8: Universal Models [Fa’14]

Show that any two-dimensional Turing machine that can add an delete rows can be
simulated by a standard Turing machine.
4. A binary-tree Turing machine uses an infinite binary tree as its tape; that is, every cell inthe tape has a left child and a right child. At each step, the head moves from its current
cell to its Parent, its Left child, or to its Right child. Thus, the transition function of such amachine has the form δ : Q × Γ → Q × Γ × {P, L, R}. The input string is initially given along
the left spine of the tape.
Show that any binary-tree Turing machine can be simulated by a standard Turingmachine.
5. A stack-tape Turing machine uses an semi-infinite tape, where every cell is actually the
top of an independent stack. The behavior of the machine at each iteration is governed by
its internal state and the symbol at the top of the current cell’s stack. At each transition,
the head can optionally push a new symbol onto the stack, or pop the top symbol off thestack. (If a stack is empty, its “top symbol” is a blank and popping has no effect.)Show that any stack-tape Turing machine can be simulated by a standard Turingmachine. (Compare with Problem ??!)
6. A tape-stack Turing machine has two actions that modify its work tape, in addition tosimply writing individual cells: it can save the entire tape by pushing in onto a stack, and it
can restore the entire tape by popping it off the stack. Restoring a tape returns the content
of every cell to its content when the tape was saved. Saving and restoring the tape do notchange the machine’s state or the position of its head. If the machine attempts to “restore”
the tape when the stack is empty, the machine crashes.
Show that any tape-stack Turing machine can be simulated by a standard Turingmachine.

ÆÆÆ• Tape alphabet = N.

– Read: zero or positive. Write: +1, −1– Read: even or odd. Write: +1, −1, ×2, ÷2– Read: positive, negative, or zero. Write: x + y (merge), x − y (merge), 1, 0

• Never three times in a row in the same direction• Hole-punch TM: tape alphabet {, }, and only  7→  transitions allowed.

© Copyright 2017 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/ for the most recent revision.

8