Variants of Turing Machine

Variants of Turing Machine

1. Costas Busch - RPI 1
Variations
of the
Turing Machine

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

3. Costas Busch - RPI 3
Same Power of two classes means:
For any machine of first class
1
M
there is a machine of second class
2
M
such that:
)()(
21
MLML =
And vice-versa

4. Costas Busch - RPI 4
Turing Machines with Stay-Option
The head can stay in the same position
ààaa c àààba cbbaa
Left, Right, Stay
L,R,S: moves

5. Costas Busch - RPI 5
Example:
ààaa c àààba cbbaa
Time 1
ààba c àààba cbbaa
Time 2
1
q
2
q
1
q
2
q
Sba,®

6. Costas Busch - RPI 6
1
q
2
q
Sba,®
1
q
2
q
Lba,®
3
q
Rxx,®
Stay-Option Machine
Simulation in Standard Machine
For every symbol x

7. Costas Busch - RPI 7
Example
à àaaba
1
q
Stay-Option Machine:
1
à àbaba
2
q
2
1
q
2
q
Sba,®
Simulation in Standard Machine:
à àaaba
1
q
1
à àbaba
2
q
2
à àbaba
3
q
3

8. Costas Busch - RPI 8
Standard Machine--Multiple Track Tape
à
à
à
à
à
à
b
d
a
b
b
a
a
c
track 1
track 2
one symbol

9. Costas Busch - RPI 9
Semi-Infinite Tape
.........
#abacàà

10. Costas Busch - RPI 10
The Off-Line Machine
Control Unit
Input File
Tape
read-only
abc
deg àààà
read-write

11. Costas Busch - RPI 11
1. Copy input file to tape
Input File
abc ààà
Tape
abcà àà
Standard machine
Off-line machine
abc

12. Costas Busch - RPI 12
2. Do computations as in Turing machine
Input File
abc ààà
Tape
abcà àà
abc
1
q
1
q
Standard machine
Off-line machine

13. Costas Busch - RPI 13
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

14. Costas Busch - RPI 14
Multitape Turing Machines
ààabc ààefg
Control unit
Tape 1 Tape 2
Input

15. Costas Busch - RPI 15
ààabc ààefg
1
q
1
q
ààagc ààed
g
2
q
2
q
Time 1
Time 2
RLdgfb ,),,(),(®
1
q
2
q
Tape 1 Tape 2

16. Costas Busch - RPI 16
Same power doesn’t imply same speed:
Language
}{
nn
baL=
Acceptance Time
Standard machine
Two-tape machine
2
n
n

17. Costas Busch - RPI 17
NonDeterministic Turing Machines
Lba,®
Rca,®
1
q
2
q
3
q
Non Deterministic Choice

18. Costas Busch - RPI 18
abcà à
1
q
Lba,®
Rca,®
1
q
2
q
3
q
Time 0
Time 1
bbcà à
2
q
cbcà à
3
q
Choice 1 Choice 2

19. Costas Busch - RPI 19
Input string is accepted if
this a possible computation
w
yqxwq
f
*

0
Initial configuration Final Configuration
Final state

20. Costas Busch - RPI 20
Non-Deterministic Choices
Computation 1
1
q
2
q
4
q
3
q
5
q
6
q
7
q

21. Costas Busch - RPI 21
Non-Deterministic Choices
Computation 2
1
q
2
q
4
q
3
q
5
q
6
q
7
q

22. Costas Busch - RPI 22
Theorem: NonDeterministic Machines
have the same power with
Deterministic machines

23. Costas Busch - RPI 23
Remark:
The simulation in the Deterministic machine
takes time exponential time compared
to the NonDeterministic machine