Slide 1
Universal
Turing Machine
Sections 17.6 – 17.7
The Universal Turing Machine
Universal Turing Machine:
A programmable TM that accepts as input:
program input string
It executes the program, and produces the output:
output string
The Universal Turing Machine
To formally define the Universal Turing Machine U we need to:
1. Define an encoding operation for TMs.
2. Describe the operation of U given input
encoding of:
● a TM M, and
● an input string w.
Encoding a Turing Machine M
We need to describe M = (K, , , , s, H) as a string:
The states
The tape alphabet
The transitions
Encoding the States
Let i be log2(|K|).
Number the states from 0 to |K|-1 in binary:
Number s, the start state, 0.
Number the others in any order.
If t is the binary number assigned to state t, then:
If t is the halting state y, assign it the string yt.
If t is the halting state n, assign it the string nt.
If t is any other state, assign it the string qt.
Example of Encoding the States
Suppose M has 9 states.
i = 4
s = q0000,
Remaining states (where y is 3 and n is 4):
q0001, q0010, y0011, n0100,
q0101, q0110, q0111, q1000
Encoding a Turing Machine M (cont’d)
The tape alphabet:
ax : x {0, 1}+,
|x| = j, and
j is the smallest integer such that 2j ||.
(j = log2(||))
Example: = {q, a, b, c}. j = 2.
q = a00
a = a01
b = a10
c = a11
The transitions: (state, input, state, output, move)
Example: (q000,a000,q110,a000,)
Encoding a Turing Machine M (cont’d)
An Encoding Example
Consider M = ({s, q, h}, {a, b, c}, {q, a, b, c}, , s, {h}):
(q00,a10,q01,a01,), (q00,a11,q01,a10,),
(q01,a00,q00,a01,), (q01,a01,q01,a10,),
(q01,a10,q01,a11,), (q01,a11,h11,a01,)
state symbol
s q (q,q, )
s a (s,b,)
s b (q,a, )
s c (q,b, )
q q (s,a, )
q a (q,b,)
q b (q,b, )
q c (h,a, )
state/symbol representation
s q00
q q01
h h10
q a00
a a01
b a10
c a11
Enumerating Turing Machines
Theorem: There exists an infinite lexicographic enumeration of:
(a) All syntactically valid TMs.
(b) All syntactically valid TMs with specific input alphabet .
(c) All syntactically valid TMs with specific input alphabet and specific tape alphabet .
Enumerating Turing Machines
Proof: Fix = {(, ), a, q, y, n, 0, 1, comma, , }, ordered as listed. Then:
1. Lexicographically enumerate the strings in *.
2. As each string s is generated, check to see whether
it is a syntactically valid Turing machine description.
If it is, output it.
To restrict the enumeration to symbols in sets and , check, in step 2, that only alphabets of the appropriate sizes are allowed.
We can now talk about the ith Turing machine.
Another Win of Encoding
One big win of defining a way to encode any Turing machine M:
● We can talk about operations on programs (TMs).
Example of a Transforming TM T:
Input: a TM M1 that reads its input tape and performs some operation P on it.
Output: a TM M2 that performs P on an empty input tape.
Encoding Multiple Inputs
Let:
mean a single string that encodes the sequence of individual values:
x1, x2, …xn.
On input
● Halt iff M halts on w.
● If M is a deciding or semideciding machine, then:
● If M accepts, accept.
● If M rejects, reject.
● If M computes a function, then U(
The Specification of the Universal TM
U will use 3 tapes:
● Tape 1: M’s tape.
● Tape 2:
● Tape 3: M’s state.
How U Works
The Universal TM
Initialization of U:
1. Copy
2. Look at
s on tape 3.
After initialization:
40.unknown
41.unknown
The Operation of U
Simulate the steps of M :
1. Until M would halt do:
1.1 Scan tape 2 for a quintuple that matches the
(current state, input) pair.
1.2 Perform the associated action, by changing tapes 1 and 3. If
necessary, extend the tape.
1.3 If no matching quintuple found, halt. Else loop.
2. Report the same result M would report.
42.unknown