Turing’s Thesis
Courtesy Costas Busch - RPI
1
Turing’s thesis:
Any computation carried out
by mechanical means
can be performed by a Turing Machine
(1930)
Courtesy Costas Busch - RPI
2
Computer Science Law:
A computation is mechanical
if and only if
it can be performed by a Turing Machine
There is no known model of computation
more powerful than Turing Machines
Courtesy Costas Busch - RPI
3
Definition of Algorithm:
An algorithm for function f (w)
is a
Turing Machine which computes f (w)
Courtesy Costas Busch - RPI
4
Algorithms are Turing Machines
When we say:
There exists an algorithm
We mean:
There exists a Turing Machine
that executes the algorithm
Courtesy Costas Busch - RPI
5
Variations
of the
Turing Machine
Courtesy Costas Busch - RPI
6
The Standard Model
Infinite Tape
 aababb cac a
Read-Write Head
(Left or Right)
Control Unit
Deterministic
Courtesy Costas Busch - RPI
7
Variations of the Standard Model
Turing machines with: • Stay-Option
• Semi-Infinite Tape
• Off-Line
• Multitape
• Multidimensional
• Nondeterministic
Courtesy Costas Busch - RPI
8
The variations form different
Turing Machine Classes
We want to prove:
Each Class has the same
power with the Standard Model
Courtesy Costas Busch - RPI
9
Same Power of two classes means:
Both classes of Turing machines accept
the same languages
Courtesy Costas Busch - RPI
10
Same Power of two classes means:
For any machine
M1
there is a machine
such that:
of first class
M2
of second class
L( M1)  L( M 2 )
And vice-versa
Courtesy Costas Busch - RPI
11
Simulation: a technique to prove same power
Simulate the machine of one class
with a machine of the other class
First Class
Original Machine
Second Class
Simulation Machine
M2
M1
M1
Courtesy Costas Busch - RPI
12
Configurations in the Original Machine
correspond to configurations
in the Simulation Machine
Original Machine:
Simulation Machine:
d0  d1    d n



d 0  d1    d n
Courtesy Costas Busch - RPI
13
Final Configuration
Original Machine:
df
Simulation Machine:
d f
The Simulation Machine
and the Original Machine
accept the same language
Courtesy Costas Busch - RPI
14
Turing Machines with Stay-Option
The head can stay in the same position
 aababb cac a
Left, Right, Stay
L,R,S: moves
Courtesy Costas Busch - RPI
15
Example:
Time 1
 aababb cac a
q1
Time 2
 b ab ab b c ac a
q2
q1
a  b, S
Courtesy Costas Busch - RPI
q2
16
Theorem:
Stay-Option Machines
have the same power with
Standard Turing machines
Courtesy Costas Busch - RPI
17
Proof:
Part 1: Stay-Option Machines
are at least as powerful as
Standard machines
Proof: a Standard machine is also
a Stay-Option machine
(that never uses the S move)
Courtesy Costas Busch - RPI
18
Proof:
Part 2: Standard Machines
are at least as powerful as
Stay-Option machines
Proof:
a standard machine can simulate
a Stay-Option machine
Courtesy Costas Busch - RPI
19
Stay-Option Machine
q1
a  b, L
q2
Simulation in Standard Machine
q1
a  b, L
q2
Similar for Right moves
Courtesy Costas Busch - RPI
20
Stay-Option Machine
q1
a  b, S
q2
Simulation in Standard Machine
q1
a  b, L
q2
x  x, R
q3
For every symbol
Courtesy Costas Busch - RPI
x
21
Example
Stay-Option Machine:
q1 a  b, S q2
1
aaba 
q1
2
baba 
q2
Simulation in Standard Machine:
1
aaba 
q1
2
baba 
q2
Courtesy Costas Busch - RPI
3
baba 
q3
22
Standard Machine--Multiple Track Tape
  a b a b 
  b a c d 
track 1
track 2
one symbol
Courtesy Costas Busch - RPI
23
track 1
  a b a b 
  b a c d 
track 2
q1
track 1
  a c a b 
  b d c d 
track 2
q2
q1
(b, a)  (c, d ), L
Courtesy Costas Busch - RPI
q2
24
Semi-Infinite Tape
# a b a c  
Courtesy Costas Busch - RPI
.........
25
Standard Turing machines simulate
Semi-infinite tape machines:
Trivial
Courtesy Costas Busch - RPI
26
Semi-infinite tape machines simulate
Standard Turing machines:
.........
Standard machine
.........
Semi-infinite tape machine
.........
Courtesy Costas Busch - RPI
27
.........
Standard machine
 a b c d e  
.........
reference point
Semi-infinite tape machine with two tracks
Right part # d e
Left part
  
# c b a  
Courtesy Costas Busch - RPI
.........
28
Standard machine
q1
q2
Semi-infinite tape machine
Left part
L
q1
L
q2
Courtesy Costas Busch - RPI
Right part
R
q1
R
q2
29
Standard machine
q1
a  g, R
q2
Semi-infinite tape machine
Right part
R
q1
Left part
L
q1
(a, x)  ( g , x), R
( x, a)  ( x, g ), L
For all symbols
Courtesy Costas Busch - RPI
R
q2
L
q2
x
30
Time 1
Standard machine
.........
.........
 a b c d e  
q1
Semi-infinite tape machine
Right part # d e
Left part
  
# c b a  
L
q1
Courtesy Costas Busch - RPI
.........
31
Time 2
Standard machine
.........
.........
 g b c d e  
q2
Semi-infinite tape machine
Right part # d e
Left part
  
# c b g  
L
q2
Courtesy Costas Busch - RPI
.........
32
At the border:
Semi-infinite tape machine
Right part
R
q1
Left part
L
q1
(# , # )  (# , # ), R
(# , # )  (# , # ), R
Courtesy Costas Busch - RPI
L
q1
R
q1
33
Semi-infinite tape machine
Time 1
Right part # d e
Left part
  
# c b g  
.........
L
q1
Time 2
Right part # d e
Left part
  
# c b g  
R
q1
Courtesy Costas Busch - RPI
.........
34
Theorem:
Semi-infinite tape machines
have the same power with
Standard Turing machines
Courtesy Costas Busch - RPI
35
The Off-Line Machine
Input File
a b c
read-only
Control Unit
Tape
read-write
  g d e  
Courtesy Costas Busch - RPI
36
Off-line machines simulate
Standard Turing Machines:
Off-line machine:
1. Copy input file to tape
2. Continue computation as in
Standard Turing machine
Courtesy Costas Busch - RPI
37
Standard machine
 a b c  
Off-line machine
Input File
a b c
Tape
  a b c 
1. Copy input file to tape
Courtesy Costas Busch - RPI
38
Standard machine
 a b c  
q1
Off-line machine
Input File
a b c
Tape
  a b c 
q1
2. Do computations as in Turing machine
Courtesy Costas Busch - RPI
39
Standard Turing machines simulate
Off-line machines:
Use a Standard machine with four track tape
to keep track of
the Off-line input file and tape contents
Courtesy Costas Busch - RPI
40
Off-line Machine
Tape
Input File
  e f g 
a b c d
Four track tape -- Standard Machine
# a b
# 0 0
e f
0 1
c d
1 0
g
0
Courtesy Costas Busch - RPI
Input File
head position
Tape
head position
41
Reference point
# a b c d
# 0 0 1 0
e f g
0 1 0
Input File
head position
Tape
head position
Repeat for each state transition:
• Return to reference point
• Find current input file symbol
• Find current tape symbol
• Make transition
Courtesy Costas Busch - RPI
42
Theorem:
Off-line machines
have the same power with
Standard machines
Courtesy Costas Busch - RPI
43
Multitape Turing Machines
Control unit
Tape 1
 a b c 
Tape 2
g
f
e


Input
Courtesy Costas Busch - RPI
44
Tape 1
Time 1
Tape 2
 a b c 
g
f
e


q1
q1
Time 2
 a g c 
g
e
d


q2
q2
q1
(b, f )  ( g , d ), L, R
Courtesy Costas Busch - RPI
q2
45
Multitape machines simulate
Standard Machines:
Use just one tape
Courtesy Costas Busch - RPI
46
Standard machines simulate
Multitape machines:
Standard machine:
• Use a multi-track tape
• A tape of the Multiple tape machine
corresponds to a pair of tracks
Courtesy Costas Busch - RPI
47
Multitape Machine
Tape 1
Tape 2
g
f
e
h 

 a b c 
Standard machine with four track tape
a
0
e
0
b
1
f
0
c
0
g h
1 0
Courtesy Costas Busch - RPI
Tape 1
head position
Tape 2
head position
48
Reference point
#
#
#
#
a
0
e
0
b
1
f
0
c
0
g h
1 0
Tape 1
head position
Tape 2
head position
Repeat for each state transition:
•Return to reference point
•Find current symbol in Tape 1
•Find current symbol in Tape 2
•Make transition
Courtesy Costas Busch - RPI
49
Theorem:
Multi-tape machines
have the same power with
Standard Turing Machines
Courtesy Costas Busch - RPI
50
Same power doesn’t imply same speed:
Language
L  {a b }
n n
Acceptance Time
Standard machine
n
Two-tape machine
n
Courtesy Costas Busch - RPI
2
51
L  {a b }
n n
Standard machine:
Go back and forth n
2
Two-tape machine:
n
Copy b to tape 2
Leave
a
n
on tape 1
Compare tape 1 and tape 2
Courtesy Costas Busch - RPI
times
( n steps)
( n steps)
( n steps)
52
MultiDimensional Turing Machines
Two-dimensional tape
y

 c a

b

MOVES: L,R,U,D
U: up D: down
x
HEAD
Position: +2, -1
Courtesy Costas Busch - RPI
53
Multidimensional machines simulate
Standard machines:
Use one dimension
Courtesy Costas Busch - RPI
54
Standard machines simulate
Multidimensional machines:
Standard machine:
• Use a two track tape
• Store symbols in track 1
• Store coordinates in track 2
Courtesy Costas Busch - RPI
55
Two-dimensional machine
y

 c a

b

Standard Machine
c
a
b
1 # 1 # 2 #  1 #  1
q1
Courtesy Costas Busch - RPI
x
q1
symbols
coordinates
56
Standard machine:
Repeat for each transition
• Update current symbol
• Compute coordinates of next position
• Go to new position
Courtesy Costas Busch - RPI
57
Theorem:
MultiDimensional Machines
have the same power
with Standard Turing Machines
Courtesy Costas Busch - RPI
58
NonDeterministic Turing Machines
a  b, L
q2
q1
a  c, R
q3
Non Deterministic Choice
Courtesy Costas Busch - RPI
59
a  b, L
q2
Time 0
q1
 a b c 
a  c, R
Choice 1
q1
q3
Time 1
 b b c 
Choice 2
 c b c 
q2
q3
Courtesy Costas Busch - RPI
60
Input string w is accepted if
this a possible computation

q0 w  x q f y
Initial configuration
Final Configuration
Final state
Courtesy Costas Busch - RPI
61
NonDeterministic Machines simulate
Standard (deterministic) Machines:
Every deterministic machine
is also a nondeterministic machine
Courtesy Costas Busch - RPI
62
Deterministic machines simulate
NonDeterministic machines:
Deterministic machine:
Keeps track of all possible computations
Courtesy Costas Busch - RPI
63
Non-Deterministic Choices
q1
q3
q2
q4
q5
Computation 1
q6
q7
Courtesy Costas Busch - RPI
64
Non-Deterministic Choices
q1
q3
q2
q4
q5
q6
Computation 2
q7
Courtesy Costas Busch - RPI
65
Simulation
Deterministic machine:
• Keeps track of all possible computations
• Stores computations in a
two-dimensional tape
Courtesy Costas Busch - RPI
66
NonDeterministic machine
a  b, L
Time 0
q2
 a b c 
q1
q1
a  c, R
q3
Deterministic machine
#
#
#
#
# # #
a b c
q1
# # #
# #
#
#
#
Courtesy Costas Busch - RPI
Computation 1
67
NonDeterministic machine
Time 1
a  b, L
 b b c 
q2
 c b c 
q2
q1
a  c, R
q3
Choice 1
Choice 2
q3
Deterministic machine
# # # #
#
b b c
# q2
#
c b c
q3
#
# #
#
#
#
#
Courtesy Costas Busch - RPI
Computation 1
Computation 2
68
Repeat
• Execute a step in each computation:
• If there are two or more choices
in current computation:
1. Replicate configuration
2. Change the state in the replica
Courtesy Costas Busch - RPI
69
Theorem: NonDeterministic Machines
have the same power with
Deterministic machines
Courtesy Costas Busch - RPI
70
Remark:
The simulation in the Deterministic machine
takes exponential time compared
to the NonDeterministic machine
Courtesy Costas Busch - RPI
71
Descargar

Languages and Finite Automata