A Universal Turing Machine
Prof. Busch - LSU
1
A limitation of Turing Machines:
Turing Machines are “hardwired”
they execute
only one program
Real Computers are re-programmable
Prof. Busch - LSU
2
Solution:
Universal Turing Machine
Attributes:
• Reprogrammable machine
• Simulates any other Turing Machine
Prof. Busch - LSU
3
Universal Turing Machine
simulates any Turing Machine M
Input of Universal Turing Machine:
Description of transitions of M
Input string of M
Prof. Busch - LSU
4
Tape 1
Three tapes
Description of M
Universal
Turing
Machine
Tape 2
Tape Contents of M
Tape 3
Prof. Busch - LSU
State of M
5
Tape 1
Description of M
We describe Turing machine M
as a string of symbols:
We encode M
as a string of symbols
Prof. Busch - LSU
6
Alphabet Encoding
Symbols:
a
b
c
d
Encoding:
1
11
111
1111
Prof. Busch - LSU

7
State Encoding
States:
q1
Encoding:
1
q2
11
q3
q4
111
1111

Head Move Encoding
Move:
L
R
Encoding:
1
11
Prof. Busch - LSU
8
Transition Encoding
Transition:
 ( q1 , a )  ( q 2 , b , L )
Encoding:
1 0 1 0 11 0 11 0 1
separator
Prof. Busch - LSU
9
Turing Machine Encoding
Transitions:
 ( q1 , a )  ( q 2 , b , L )
 ( q 2 , b )  ( q3 , c , R )
Encoding:
1 0 1 0 11 0 11 0 1 00 11 0 1 10 111 0 111 0 11
separator
Prof. Busch - LSU
10
Tape 1 contents of Universal Turing Machine:
binary encoding
of the simulated machine M
Tape 1
1 0 1 0 11 0 11 0 10011 0 1 10 111 0 111 0 1100 
Prof. Busch - LSU
11
A Turing Machine is described
with a binary string of 0’s and 1’s
Therefore:
The set of Turing machines
forms a language:
each string of this language is
the binary encoding of a Turing Machine
Prof. Busch - LSU
12
Language of Turing Machines
(Turing Machine 1)
L = { 010100101,
00100100101111,
111010011110010101,
(Turing Machine 2)
……
…… }
Prof. Busch - LSU
13
Countable Sets
Prof. Busch - LSU
14
Infinite sets are either:
Countable
or
Uncountable
Prof. Busch - LSU
15
Countable set:
There is a one to one correspondence
of
elements of the set
to
Natural numbers (Positive Integers)
(every element of the set is mapped to a number
such that no two elements are mapped to same number)
Prof. Busch - LSU
16
Example: The set of even integers
is countable
Even integers:
(positive)
0, 2, 4, 6, 
Correspondence:
Positive integers:
1, 2 , 3, 4 , 
2 n corresponds to n  1
Prof. Busch - LSU
17
Example: The set of rational numbers
is countable
Rational numbers:
1
,
2
Prof. Busch - LSU
3
4
,
7
, 
8
18
Naïve Approach
Rational numbers:
Nominator 1
1 1 1
, , ,
1 2 3
Correspondence:
Positive integers:
1, 2 , 3, 
Doesn’t work:
we will never count
numbers with nominator 2:
Prof. Busch - LSU
2
1
,
2
2
,
2
,
3
19
Better Approach
1
1
1
1
1
2
3
4
2
2
2
1
2
3
3
3
1
2
4
1




Prof. Busch - LSU
20
1
1
1
1
1
2
3
4
2
2
2
1
2
3
3
3
1
2
4
1




Prof. Busch - LSU
21
1
1
1
1
1
2
3
4
2
2
2
1
2
3
3
3
1
2
4
1




Prof. Busch - LSU
22
1
1
1
1
1
2
3
4
2
2
2
1
2
3
3
3
1
2
4
1




Prof. Busch - LSU
23
1
1
1
1
1
2
3
4
2
2
2
1
2
3
3
3
1
2
4
1




Prof. Busch - LSU
24
1
1
1
1
1
2
3
4
2
2
2
1
2
3
3
3
1
2
4
1




Prof. Busch - LSU
25
Rational Numbers:
1
1
,
1
2
,
2
1
,
1
3
,
2
, 
2
Correspondence:
Positive Integers:
1, 2 , 3 , 4 , 5 , 
Prof. Busch - LSU
26
We proved:
the set of rational numbers is countable
by describing an enumeration procedure
(enumerator)
for the correspondence to natural numbers
Prof. Busch - LSU
27
Definition
Let S be a set of strings (Language)
An enumerator for S is a Turing Machine
that generates (prints on tape)
all the strings of S one by one
and
each string is generated in finite time
Prof. Busch - LSU
28
strings s1 , s 2 , s 3 ,   S
Enumerator
Machine for S
output
s1 , s 2 , s 3 , 
(on tape)
Finite time:
Prof. Busch - LSU
t1 , t 2 , t 3 , 
29
Enumerator Machine
Time 0
Configuration
 
q0
prints s1
Time t1
x1 # s1
qs
Prof. Busch - LSU
30
Time t 2
prints s 2
x2 # s2
qs
Time t 3
prints s 3
x3 # s 3
qs
Prof. Busch - LSU
31
Observation:
If for a set S there is an enumerator,
then the set is countable
The enumerator describes the
correspondence of S to natural numbers
Prof. Busch - LSU
32
Example: The set of strings S  { a , b , c } 
is countable
Approach:
We will describe an enumerator for S
Prof. Busch - LSU
33
Naive enumerator:
Produce the strings in lexicographic order:
s1 
s2 

a
aa
aaa
aaaa
......
Doesn’t work:
strings starting with b
will never be produced
Prof. Busch - LSU
34
Better procedure:
Proper Order
(Canonical Order)
1. Produce all strings of length 1
2. Produce all strings of length 2
3. Produce all strings of length 3
4. Produce all strings of length 4
..........
Prof. Busch - LSU
35
s1 
s2 

a
b
c
length 1
aa
Produce strings in
Proper Order:
ab
ac
ba
bb
bc
ca
length 2
cb
cc
aaa
aab
aac
......
Prof. Busch - LSU
length 3
36
Theorem:
The set of all Turing Machines
is countable
Proof: Any Turing Machine can be encoded
with a binary string of 0’s and 1’s
Find an enumeration procedure
for the set of Turing Machine strings
Prof. Busch - LSU
37
Enumerator:
Repeat
1. Generate the next binary string
of 0’s and 1’s in proper order
2. Check if the string describes a
Turing Machine
if YES: print string on output tape
if NO: ignore string
Prof. Busch - LSU
38
Binary strings
Turing Machines
0
1
00
01

1 0 1 0 11 0 11 0 0
1 0 1 0 11 0 11 0 1
s1

s2
1 0 11 0 1010010101
101

1 0 1 0 11 0 11 0 1
1 0 11 0 1010010101
101
End of Proof
Prof. Busch - LSU
39
Uncountable Sets
Prof. Busch - LSU
40
We will prove that there is a language L 
which is not accepted by any Turing machine
Technique:
Turing machines are countable
Languages are uncountable
(there are more languages than Turing Machines)
Prof. Busch - LSU
41
Definition:
A set is uncountable
if it is not countable
We will prove that there is a language
which is not accepted by any Turing machine
Prof. Busch - LSU
42
Theorem:
If S is an infinite countable set, then
the powerset 2
S
of S is uncountable.
(the powerset 2 S is the set whose elements
are all possible sets made from the elements of S )
Prof. Busch - LSU
43
Proof:
Since S is countable, we can write
S  { s1 , s 2 , s 3 ,  }
Elements of S
Prof. Busch - LSU
44
Elements of the powerset 2 S have the form:

{ s1 , s 3 }
{ s 5 , s 7 , s 9 , s10 }
……
Prof. Busch - LSU
45
We encode each element of the powerset
with a binary string of 0’s and 1’s
Powerset
element
Binary encoding
s1
s2
s3
s4 
{ s1 }
1
0
0
0

{s2 ,s 3 }
0
1
1
0

{ s1 , s 3 , s 4 }
1
0
1
1

(in arbitrary order)
Prof. Busch - LSU
46
Observation:
Every infinite binary string corresponds
to an element of the powerset:
Example:
10 0 111 0 
Corresponds to: { s1 , s 4 , s 5 , s 6 ,  }  2
Prof. Busch - LSU
S
47
Let’s assume (for contradiction)
S
that the powerset 2 is countable
Then:
we can enumerate
the elements of the powerset
2
S
 {t1 , t 2 , t 3 ,  }
Prof. Busch - LSU
48
suppose that this is the respective
Powerset
element
Binary encoding
t1
1
0
0
0
0

t2
1
1
0
0
0

t3
1
1
0
1
0

t4
1
1
0
0
1



Prof. Busch - LSU
49
Take the binary string whose bits
are the complement of the diagonal
t1
1
0
0
0
0

t2
1
1
0
0
0

t3
1
1
0
1
0

t4
1
1
0
0
1

Binary string:
t  0011 
(birary complement of diagonal)
Prof. Busch - LSU
50
The binary string
corresponds
to an element of
S
the powerset 2 :
t  0011 
t  {s 3 , s 4 , }  2
Prof. Busch - LSU
S
51
Thus, t
must be equal to some t i
t  ti
However,
the i-th bit in the encoding of t is
the complement of the i-th bit of t i , thus:
t  ti
Contradiction!!!
Prof. Busch - LSU
52
Since we have a contradiction:
The powerset
2
S
of S is uncountable
End of proof
Prof. Busch - LSU
53
An Application: Languages
Consider Alphabet : A  { a , b }
The set of all Strings:
*
S  { a , b }  {  , a , b , aa , ab , ba , bb , aaa , aab ,  }
infinite and countable
(we can enumerate the strings
in proper order)
Prof. Busch - LSU
54
Consider Alphabet : A  { a , b }
The set of all Strings:
*
S  { a , b }  {  , a , b , aa , ab , ba , bb , aaa , aab ,  }
infinite and countable
Any language is a subset of S :
L  { aa , ab , aab }
Prof. Busch - LSU
55
Consider Alphabet : A  { a , b }
The set of all Strings:
*
*
S  A  { a , b }  {  , a , b , aa , ab , ba , bb , aaa , aab ,  }
infinite and countable
The powerset of S contains all languages:
2
S
 { , {  }, { a }, { a , b }, { aa , b },..., { aa , ab , aab },  }
uncountable
Prof. Busch - LSU
56
Consider Alphabet : A  { a , b }
countable
Turing machines:
M1
M2
M3

L2
L3

accepts
Languages accepted
By Turing Machines:
L1
Denote: X  { L1 , L 2 , L3 ,  }
countable
Prof. Busch - LSU
countable
Note: X  2
S
 {a , b }
*
S

57
Languages accepted
by Turing machines:
X countable
All possible languages: 2
S
Therefore:
since
S
uncountable
X 2
X  2 , we have X  2
Prof. Busch - LSU
S
S

58
Conclusion:
There is a language L  not accepted
by any Turing Machine:
X  2
S
L   2
S
and
L  X
(Language L  cannot be described
by any algorithm)
Prof. Busch - LSU
59
Non Turing-Acceptable Languages
L
Turing-Acceptable
Languages
Prof. Busch - LSU
60
Note that:
X  { L1 , L 2 , L3 ,  }
is a multi-set (elements may repeat)
since a language may be accepted
by more than one Turing machine
However, if we remove the repeated elements,
the resulting set is again countable since every element
still corresponds to a positive integer
Prof. Busch - LSU
61
Descargar

Languages and Finite Automata