FIT2014 Theory of Computation Lecture 19 Universal Turing Machines
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 19
Universal Turing Machines
slides by
based in part on previous slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 20
Overview
I Tables for Turing Machines
I Encoding
I Decoding
I Definition of a Universal Turing Machine
I Algorithm for a Universal Turing Machine
I Existence of Universal Turing Machines
2 / 20
Assumptions
I Input Alphabet: {a,b}
I Tape Alphabet: {a,b,#}
I Start State: numbered 1
I Accept State: numbered 2
3 / 20
Tables for TMs
1 23 4
a→ R
b→ R
b→ R ∆→ R
From To Read Write Move
1 3 a a R
1 3 b b R
3 4 b b R
4 2 ∆ ∆ R
4 / 20
TM for {anbnan : n ≥ 0}
12
3 4 5
6
789
∆→ R
a→ A,R
b→ R a→ L
b→ a,R
∆→ L
a→ ∆, La→ ∆, L
A→ R
a→ R b→ R
a→ R
a→ L
b→ L
5 / 20
Table
From To Read Write Move
1 3 a # R
3 3 a a R
3 4 b b R
4 4 b b R
4 5 a a L
5 6 b a R
6 6 a a R
6 7 ∆ ∆ L
7 8 a ∆ L
8 9 a ∆ L
9 9 a a L
9 9 b b L
9 1 # # R
1 2 ∆ ∆ R
6 / 20
Conditions to Check
Check whether there is a row with a 1 in the From column.
Check that there is no row with a 2 in the From column.
Check there are no two rows with the same numbers in the From and the same letter
in the Read column.
7 / 20
Coding
State
number Code
n anb
Letter Code
a aa
b ab
∆ ba
# bb
Direction Code
L a
R b
8 / 20
Coding the Table
From To Read Write Move Code
1 3 a # R abaaabaabbb
3 3 a a R aaabaaabaaaab
3 4 b b R aaabaaaabababb
4 4 b b R aaabaaaabababb
4 5 a a L aaaabaaaaabaaaaa
5 6 b a R aaaaabaaaaaababaab
6 6 a a R aaaaaabaaaaaabaaaab
6 7 ∆ ∆ L aaaaaabaaaaaaabbabaa
7 8 a ∆ L aaaaaaabaaaaaaaabaabaa
8 9 a ∆ L aaaaaaaabaaaaaaaaabaabaa
9 9 a a L aaaaaaaaabaaaaaaaaabaaaaa
9 9 b b L aaaaaaaaabaaaaaaaaabababa
9 1 # # R aaaaaaaaababbbbbb
1 2 ∆ ∆ R abaabbabab
9 / 20
Encoding of the TM
abaaabaabbbaaabaaabaaaabaaabaaaabababbaaabaaaabababbaaaabaaaaabaaaaa
aaaaabaaaaaababaabaaaaaabaaaaaabaaaabaaaaaabaaaaaaabbabaa
aaaaaaabaaaaaaaabaabaaaaaaaaaabaaaaaaaaabaabaaaaaaaaaaabaaaaaaaaabaaaaa
aaaaaaaaabaaaaaaaaabababaaaaaaaaaababbbbbbabaabbabab
. . . as one long string, without breaks or spaces.
10 / 20
Code Word Language (CWL)
The Code-Word Language (CWL) is the regular language defined by the regular
expression
(aa∗baa∗b(a ∪ b)5)∗
Words which encode a TM belong to CWL.
BUT: Not all words in CWL encode a TM.
Quantifier practice:
¬∀w ∈ CWL ∃M : w encodes M
∃w ∈ CWL ¬∃M : w encodes M
∃w ∈ CWL ∀M : ¬ (w encodes M)
∃w ∈ CWL ∀M : w does not encode M
11 / 20
Decode
abaaabaaaababaaabababbaaabaaaabababbaaaabaabbabab
From To Read Write Move
1 3 a a R
1 3 b b R
3 4 b b R
4 2 ∆ ∆ R
12 / 20
Algorithm
While there are unread letters
1. Read and count the next clump of a’s, then read the b after it.
I Interpret clump of a’s as the state number, in unary, that this transition goes from.
2. Read and count the next clump of a’s, then read the b after it.
I Interpret clump of a’s as the state number, in unary, that this transition goes to.
3. Read the next two letters.
I Interpret it as the letter to be read for this transition.
4. Read the next two letters.
I Interpret it as the letter to be written for this transition.
5. Read the next letter.
I Interpret it as the direction for this transition.
13 / 20
Universal Turing Machine (UTM)
Definition
A Universal Turing Machine (UTM) is a Turing Machine
that takes, as input,
I an encoding of some Turing Machine M, together with
I a string x , to be used as input to M
and simulates the execution of M on x .
14 / 20
Example
1 23
b→ R
a→ R a→ R
Suppose we want a UTM to simulate the execution of this TM on the string bbbaa.
Input to the UTM:
Turing Machine: abaaabaaaabababababbaaabaabaaaab
Data: bbbaa
15 / 20
Input for UTM
a b a a a b a a a a b a b a b a b a b b a b a a a b a a a a b $ b b b a a∆∆∆ . . .
Turing Machine (encoded)︷ ︸︸ ︷
input for the
encoded TM︷ ︸︸ ︷
input for the UTM︷ ︸︸ ︷
marks end of
TM encoding
and start of
its input
16 / 20
Algorithm for a UTM
1. Move rightwards to first letter of the encoded TM’s input.
Read it. Mark it, so we can come back to it (e.g., a 7→ A, b 7→ B).
I Remember it (in choice of state).
2. Move leftwards to first instruction.
3. If the next state in current instruction in encoded TM is the Accept state
Find (from current instruction) what to write and direction of next move.
Remember it (in choice of state).
Move rightwards back to current position in encoded TM’s input.
Write the required letter, move in the required direction, and Accept.
else
Find (from current instruction) what to write and direction of next move.
Remember it (in choice of state).
Move rightwards back to current position in encoded TM’s input.
Write the required letter, move in the required direction.
Read current letter in encoded TM’s input. Mark it, so we can come back to it.
Remember it (in choice of state).
Move leftwards to find the next instruction (using remembered letter).
17 / 20
Exercise
Suppose:
I U is a UTM,
I T is a TM
I x is an input string for T , with |x | = n.
I When T is run on input x , it takes time t and visits at most s tape cells.
Using the algorithm outline of the previous slide, and the encoding scheme for TMs
given in this lecture:
I Determine an upper bound for the time taken by U to simulate the running of T
on input x .
I Give the bound in terms of t, s and n.
18 / 20
Importance of UTMs
I theoretical model of one computer simulating another
I Stored-program computer
I von Neumann architecture
19 / 20
Revision
I Know how to encode a Turing Machine.
I Know how to decode Turing Machine representation.
I Know what a Universal Turing Machine is, and what it does.
I Understand why UTMs exist.
20 / 20