Turing’s Thesis
Fall 2006
Costas Busch - RPI
1
Turing’s thesis (1930):
Any computation carried out
by mechanical means
can be performed by a Turing Machine
Fall 2006
Costas Busch - RPI
2
Algorithm:
An algorithm for a problem is a
Turing Machine which solves the problem
The algorithm describes the steps of
the mechanical means
This is easily translated to computation steps
of a Turing machine
Fall 2006
Costas Busch - RPI
3
When we say: There exists an algorithm
We mean: There exists a Turing Machine
that executes the algorithm
Fall 2006
Costas Busch - RPI
4
Variations
of the
Turing Machine
Fall 2006
Costas Busch - RPI
5
The Standard Model
Infinite Tape
 aababb cac a
Read-Write Head
(Left or Right)
Control Unit
Deterministic
Fall 2006
Costas Busch - RPI
6
Variations of the Standard Model
Turing machines with: • Stay-Option
• Semi-Infinite Tape
• Off-Line
• Multitape
• Multidimensional
• Nondeterministic
Different Turing Machine Classes
Fall 2006
Costas Busch - RPI
7
Same Power of two machine classes:
both classes accept the
same set of languages
We will prove:
each new class has the same power
with Standard Turing Machine
(accept Turing-Recognizable Languages)
Fall 2006
Costas Busch - RPI
8
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
Fall 2006
Costas Busch - RPI
9
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
simulates
Fall 2006
Costas Busch - RPI
M1
10
Configurations in the Original Machine
have corresponding configurations
in the Simulation Machine M 2
Original Machine:
Simulation Machine:
Fall 2006
M1
M1
d0  d1    d n



d 0  d1    d n
M2
Costas Busch - RPI
11
Accepting Configuration
Original Machine:
df
Simulation Machine:
d f
the Simulation Machine
and the Original Machine
accept the same strings
L( M1)  L( M 2 )
Fall 2006
Costas Busch - RPI
12
Turing Machines with Stay-Option
The head can stay in the same position
 aababb cac a
Left, Right, Stay
L,R,S: possible head moves
Fall 2006
Costas Busch - RPI
13
Example:
Time 1
 aababb cac a
q1
Time 2
 b ab ab b c ac a
q2
q1
Fall 2006
a  b, S
Costas Busch - RPI
q2
14
Theorem: Stay-Option machines
have the same power with
Standard Turing machines
Proof: 1. Stay-Option Machines
simulate Standard Turing machines
2. Standard Turing machines
simulate Stay-Option machines
Fall 2006
Costas Busch - RPI
15
1. Stay-Option Machines
simulate Standard Turing machines
Trivial: any standard Turing machine
is also a Stay-Option machine
Fall 2006
Costas Busch - RPI
16
2. Standard Turing machines
simulate Stay-Option machines
We need to simulate the stay head option
with two head moves, one left and one right
Fall 2006
Costas Busch - RPI
17
Stay-Option Machine
q1
a  b, S
q2
Simulation in Standard Machine
q1
a  b, L
x  x, R
q2
For every possible tape symbol
Fall 2006
Costas Busch - RPI
x
18
For other transitions nothing changes
Stay-Option Machine
q1
a  b, L
q2
Simulation in Standard Machine
q1
a  b, L
q2
Similar for Right moves
Fall 2006
Costas Busch - RPI
19
example of simulation
Stay-Option Machine:
q1 a  b, S q2
1
aaba 
baba 
2
q1
q2
Simulation in Standard Machine:
1
aaba 
q1
2
baba 
q2
3
baba 
q3
END OF PROOF
Fall 2006
Costas Busch - RPI
20
Multiple Track Tape
A useful trick to perform more
complicated simulations
One Tape
  a b a b 
  b a c d 
track 1
track 2
One head
One symbol ( a, b)
Fall 2006
Costas Busch - RPI
21
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
Fall 2006
(b, a)  (c, d ), L
Costas Busch - RPI
q2
22
Semi-Infinite Tape
The head extends infinitely only to the right
a b a c  
.........
• Initial position is the leftmost cell
• When the head moves left from the border,
it returns to the same position
Fall 2006
Costas Busch - RPI
23
Theorem:
Semi-Infinite machines
have the same power with
Standard Turing machines
Proof: 1. Standard Turing machines
simulate Semi-Infinite machines
2. Semi-Infinite Machines
simulate Standard Turing machines
Fall 2006
Costas Busch - RPI
24
1. Standard Turing machines simulate
Semi-Infinite machines:
  # a b a c  
Standard Turing Machine
a. insert special symbol
#
at left of input string
b. Add a self-loop
to every state
## , R
(except states with no
outgoing transitions)
Fall 2006
Costas Busch - RPI
25
2. Semi-Infinite tape machines simulate
Standard Turing machines:
.........
Standard machine
.........
Semi-Infinite tape machine
.........
Squeeze infinity of both directions
in one direction
Fall 2006
Costas Busch - RPI
26
.........
Standard machine
 a b c d e  
.........
reference point
Semi-Infinite tape machine with two tracks
Right part # d e
Left part
Fall 2006
  
# c b a  
Costas Busch - RPI
.........
27
Standard machine
q1
q2
Semi-Infinite tape machine
Left part
L
q1
Fall 2006
Right part
L
q2
R
q1
Costas Busch - RPI
R
q2
28
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 tape symbols
Fall 2006
Costas Busch - RPI
x
R
q2
L
q2
29
Time 1
Standard machine
.........
.........
 a b c d e  
q1
Semi-Infinite tape machine
Right part # d e
Left part
Fall 2006
  
# c b a  
L
q1
Costas Busch - RPI
.........
30
Time 2
Standard machine
.........
.........
 g b c d e  
q2
Semi-Infinite tape machine
Right part # d e
Left part
Fall 2006
  
# c b g  
L
q2
Costas Busch - RPI
.........
31
At the border:
Semi-Infinite tape machine
Right part
R
q1
Left part
L
q1
Fall 2006
(# , # )  (# , # ), R
(# , # )  (# , # ), R
Costas Busch - RPI
L
q1
R
q1
32
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
Fall 2006
.........
END OF PROOF
Costas Busch - RPI
33
The Off-Line Machine
Input File read-only (once)
a b c
Input string
Control Unit
Input string
Appears on
input file only
(state machine)
Tape
read-write
  g d e  
Fall 2006
Costas Busch - RPI
34
Theorem: Off-Line machines
have the same power with
Standard Turing machines
Proof: 1. Off-Line machines
simulate Standard Turing machines
2. Standard Turing machines
simulate Off-Line machines
Fall 2006
Costas Busch - RPI
35
1. Off-line machines simulate
Standard Turing Machines
Off-line machine:
1. Copy input file to tape
2. Continue computation as in
Standard Turing machine
Fall 2006
Costas Busch - RPI
36
Standard machine
 a b c  
Off-line machine
Tape
Input File
  a b c 
a b c
1. Copy input file to tape
Fall 2006
Costas Busch - RPI
37
Standard machine
 a b c  
q1
Off-line machine
Tape
Input File
  a b c 
a b c
q1
2. Do computations as in Turing machine
Fall 2006
Costas Busch - RPI
38
2. Standard Turing machines simulate
Off-Line machines:
Use a Standard machine with
a four-track tape to keep track of
the Off-line input file and tape contents
Fall 2006
Costas Busch - RPI
39
Off-line Machine
Tape
Input File
  e f g 
a b c d
Standard Machine -- Four track tape
# a b
# 0 0
e f
0 1
Fall 2006
c d
1 0
g
0
Costas Busch - RPI
Input File
head position
Tape
head position
40
Reference point
#
#
#
#
a
0
e
0
b
0
f
1
(uses special symbol # )
c d
1 0
g
0
Input File
head position
Tape
head position
Repeat for each state transition:
1. Return to reference point
2. Find current input file symbol
3. Find current tape symbol
4. Make transition
Fall 2006
Costas Busch - RPI
END OF PROOF
41
Multi-tape Turing Machines
Control unit
(state machine)
Tape 1
Tape 2
g
f
e


 a b c 
Input string
Input string appears on Tape 1
Fall 2006
Costas Busch - RPI
42
Tape 1
Time 1
Tape 2
 a b c 
g
f
e


q1
q1
Tape 1
Time 2
g
e
d


 a g c 
q2
q2
q1
Fall 2006
Tape 2
(b, f )  ( g , d ), L, R
Costas Busch - RPI
q2
43
Theorem: Multi-tape machines
have the same power with
Standard Turing machines
Proof: 1. Multi-tape machines
simulate Standard Turing machines
2. Standard Turing machines
simulate Multi-tape machines
Fall 2006
Costas Busch - RPI
44
1. Multi-tape machines simulate
Standard Turing Machines:
Trivial: Use just one tape
Fall 2006
Costas Busch - RPI
45
2. Standard Turing machines simulate
Multi-tape machines:
Standard machine:
• Uses a multi-track tape to simulate
the multiple tapes
• A tape of the Multi-tape machine
corresponds to a pair of tracks
Fall 2006
Costas Busch - RPI
46
Multi-tape Machine
Tape 1
Tape 2
g
f
e
h 

 a b c 
Standard machine with four track tape
a
0
e
0
Fall 2006
b
1
f
0
c
0
g h
1 0
Costas Busch - RPI
Tape 1
head position
Tape 2
head position
47
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:
1. Return to reference point
2. Find current symbol in Tape 1
3. Find current symbol in Tape 2
4. Make transition
Fall 2006
Costas Busch - RPI
END OF PROOF
48
Same power doesn’t imply same speed:
n n
L  {a b }
2
Standard Turing machine: O ( n ) time
2
O
(
n
) times
Go back and forth
to match the a’s with the b’s
2-tape machine: O(n) time
n
1. Copy b to tape 2
(O(n) steps)
n
2. Compare a on tape 1
and
Fall 2006
n
b tape 2
Costas Busch - RPI
(O(n) steps)
49
Multidimensional Turing Machines
2-dimensional tape
y

 c a

b

MOVES: L,R,U,D
U: up D: down
Fall 2006
x
HEAD
Position: +2, -1
Costas Busch - RPI
50
Theorem: Multidimensional machines
have the same power with
Standard Turing machines
Proof: 1. Multidimensional machines
simulate Standard Turing machines
2. Standard Turing machines
simulate Multi-Dimensional machines
Fall 2006
Costas Busch - RPI
51
1. Multidimensional machines simulate
Standard Turing machines
Trivial: Use one dimension
Fall 2006
Costas Busch - RPI
52
2. Standard Turing machines simulate
Multidimensional machines
Standard machine:
• Use a two track tape
• Store symbols in track 1
• Store coordinates in track 2
Fall 2006
Costas Busch - RPI
53
2-dimensional machine
y

 c a

b

Standard Machine
c
a
b
1 # 1 # 2 #  1 #  1
q1
Fall 2006
Costas Busch - RPI
x
q1
symbols
coordinates
54
Standard machine:
Repeat for each transition followed
in the 2-dimensional machine:
1. Update current symbol
2. Compute coordinates of next position
3. Go to new position
END OF PROOF
Fall 2006
Costas Busch - RPI
55
Nondeterministic Turing Machines
a  b, L
q2
Choice 1
q1
a  c, R
q3 Choice 2
Allows Non Deterministic Choices
Fall 2006
Costas Busch - RPI
56
Time 0
 a b c 
Time 1
q1
a  b, L
Choice 1
q2
 b b c 
q2
q1
a  c, R
Fall 2006
Choice 2
q3
 c b c 
Costas Busch - RPI
q3
57
Input string w is accepted if
there is a computation:

q0 w  x q f y
Initial configuration
Final Configuration
Any accept state
There is a computation:
Fall 2006
Costas Busch - RPI
58
Theorem: Nondeterministic machines
have the same power with
Standard Turing machines
Proof: 1. Nondeterministic machines
simulate Standard Turing machines
2. Standard Turing machines
simulate Nondeterministic machines
Fall 2006
Costas Busch - RPI
59
1. Nondeterministic Machines simulate
Standard (deterministic) Turing Machines
Trivial: every deterministic machine
is also nondeterministic
Fall 2006
Costas Busch - RPI
60
2. Standard (deterministic) Turing machines
simulate Nondeterministic machines:
Deterministic machine:
• Uses a 2-dimensional tape
(which is equivalent to 1-dimensional tape)
• Stores all possible computations
of the non-deterministic machine
on the 2-dimensional tape
Fall 2006
Costas Busch - RPI
61
All possible computation paths
Initial state
Step 1
Step 2
Step i
reject
Fall 2006
accept
infinite
path
Costas Busch - RPI
Step i+1
62
The Deterministic Turing machine
simulates all possible computation paths:
•simultaneously
•step-by-step
•in a breadth-first search fashion
Fall 2006
Costas Busch - RPI
63
NonDeterministic machine
a  b, L
Time 0
q2
 a b c 
q1
q1
a  c, R
q3
Deterministic machine
#
#
#
#
Fall 2006
# # #
a b c
q1
# # #
# #
#
#
#
Costas Busch - RPI
current
configuration
64
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
#
Fall 2006
# #
#
#
#
#
Costas Busch - RPI
Computation 1
Computation 2
65
Deterministic Turing machine
Repeat
For each configuration in current step
of non-deterministic machine,
if there are two or more choices:
1. Replicate configuration
2. Change the state in the replicas
Until either the input string is accepted
or rejected in all configurations
END OF PROOF
Fall 2006
Costas Busch - RPI
66
Remark:
The simulation takes in the worst case
exponential time compared to the shortest
accepting path length of the
nondeterministic machine
Fall 2006
Costas Busch - RPI
67
Descargar

Languages and Finite Automata