Variations Of The Turing Machine

Variations of the Turing Machine

1

The Standard Model Infinite Tape

 aababbcac a Read-Write Head

(Left or Right)

Control Unit Deterministic

2

Variations of the Standard Model Turing machines with: • Stay-Option • Semi-Infinite Tape • Off-Line • Multitape • Multidimensional • Nondeterministic

3

The variations form different Turing Machine Classes

We want to prove: Each Class has the same power with the Standard Model 4

Same Power of two classes means: Both classes of Turing machines accept the same languages

5

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

6

Simulation: a technique to prove same power Simulate the machine of one class with a machine of the other class

First Class Original Machine

M1

Second Class Simulation Machine

M2 M1 7

Configurations in the Original Machine correspond to configurations in the Simulation Machine

Original Machine:

Simulation Machine:

d 0  d1    d n 





d 0  d1    d n 8

Final Configuration Original Machine:

df

Simulation Machine:

d f

The Simulation Machine and the Original Machine accept the same language 9

Turing Machines with Stay-Option

The head can stay in the same position

 aababbcac a Left, Right, Stay L,R,S: moves 10

Example:

Time 1

 aababbcac a q1 Time 2

 b ab abb c ac a

q2 q1

a  b, S

q2 11

Theorem:

Stay-Option Machines have the same power with Standard Turing machines

12

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) 13

Proof: Part 2: Standard Machines are at least as powerful as Stay-Option machines

Proof:

a standard machine can simulate a Stay-Option machine

14

Stay-Option Machine

q1

a  b, L

q2

Simulation in Standard Machine

q1

a  b, L

q2

Similar for Right moves 15

Stay-Option Machine

q1

a  b, S

q2

Simulation in Standard Machine

q1

a  b, L

q3

x  x, R

q2

For every symbol

x 16

Example Stay-Option Machine:

a  b , S q2 q1

1

aaba 

2

baba  q2

q1 Simulation in Standard Machine: 1

aaba  q1

2

baba  q3

3

baba  q2 17

Standard Machine--Multiple Track Tape

  a b a b    b a c d 

track 1 track 2

one symbol

18

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

q2 19

Semi-Infinite Tape

# a b a c  

.........

20

Standard Turing machines simulate Semi-infinite tape machines:

Trivial

21

Semi-infinite tape machines simulate Standard Turing machines:

.........

Standard machine

.........

Semi-infinite tape machine .........

22

.........

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 

 

.........

23

Theorem:

Semi-infinite tape machines have the same power with Standard Turing machines

24

The Off-Line Machine Input File

a b c read-only Control Unit Tape

read-write

  g d e   25

Off-line machines simulate Standard Turing Machines: Off-line machine:

1. Copy input file to tape 2. Continue computation as in Standard Turing machine

26

Standard machine

 a b c  

Off-line machine Input File

a b c

Tape

  a b c 

1. Copy input file to tape 27

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 28

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

29

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

Input File head position Tape head position 30

Theorem:

Off-line machines have the same power with Standard machines

31

Multitape Turing Machines Control unit

Tape 1

 a b c 

Tape 2

g f e  

Input

32

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

q2 33

Multitape machines simulate Standard Machines:

Use just one tape

34

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 35

Multitape Machine Tape 1 Tape 2

 a b c 

g f e h  

Standard machine with four track tape

a 0 e 0

b 1 f 0

c 0 g h 1 0

Tape 1 head position Tape 2 head position 36

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 37

Theorem:

Multi-tape machines have the same power with Standard Turing Machines

38

Same power doesn’t imply same speed: Language

L  {a b } n n

Acceptance Time Standard machine

n

Two-tape machine

n

2

39

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

times

( n steps) ( n steps) ( n steps) 40

MultiDimensional Turing Machines Two-dimensional tape

y   c a  b 

MOVES: L,R,U,D U: up D: down

x

HEAD Position: +2, -1 41

Multidimensional machines simulate Standard machines:

Use one dimension

42

Standard machines simulate Multidimensional machines:

Standard machine: • Use a two track tape

• Store symbols in track 1 • Store coordinates in track 2 43

Two-dimensional machine

y

  c a  b  Standard Machine

c a b 1 # 1 # 2 #  1 #  1 q1

x

q1 symbols coordinates 44

Standard machine:

Repeat for each transition • Update current symbol • Compute coordinates of next position • Go to new position

45

Theorem:

MultiDimensional Machines have the same power with Standard Turing Machines

46

NonDeterministic Turing Machines a  b, L

q2

q1 a  c, R

q3

Non Deterministic Choice 47

a  b, L

q2

Time 0

q1

 a b c 

a  c, R Choice 1

 b b c  q2

q1

q3 Time 1

Choice 2

 c b c  q3 48

Input string w is accepted if this a possible computation 

q0 w  x q f y Initial configuration

Final Configuration

Final state 49

NonDeterministic Machines simulate Standard (deterministic) Machines:

Every deterministic machine is also a nondeterministic machine

50

Deterministic machines simulate NonDeterministic machines:

Deterministic machine: Keeps track of all possible computations

51

Non-Deterministic Choices

q1 q3

q2 q5

q4 Computation 1

q6

q7 52

Non-Deterministic Choices

q1 q3

q2 q5

q4 q6 Computation 2

q7 53

Simulation Deterministic machine: • Keeps track of all possible computations

• Stores computations in a two-dimensional tape

54

NonDeterministic machine

a  b, L

Time 0

q2

 a b c 

q1

q1

a  c, R

q3 Deterministic machine

# # # #

# # # a b c q1 # # #

# # # # #

Computation 1

55

NonDeterministic machine Time 1

a  b, L

q2

 b b c 

Choice 1

q2

q1 a  c, R

 c b c  q3

Choice 2

q3

Deterministic machine

# # # # # # # b b c # # q2 # # c b c # q3 # #

Computation 1 Computation 2 56

Theorem: NonDeterministic Machines have the same power with Deterministic machines

57

Remark: The simulation in the Deterministic machine takes time exponential time compared to the NonDeterministic machine

58