Turing Machine

Turing Machine

1. Source of Slides: Introduction to Automata Theory, Languages, and Computation
By John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman

2. Dept. of Computer Science & IT, FUUAST
Theory of Computation
2
Turing MachineTuring Machine
Church-Turing’s ThesisChurch-Turing’s Thesis
Any mathematical problem
solving that can be described
by an algorithm can be modeled
by a Turing Machine.

3. Dept. of Computer Science & IT, FUUAST
Theory of Computation
3
Turing MachineTuring Machine
1) 1) Multiple trackMultiple track
2) Shift over Turing Machine2) Shift over Turing Machine
3) Nondeterministic3) Nondeterministic
4) Two way Turing Machine4) Two way Turing Machine
5) Multitape Turing Machine5) Multitape Turing Machine
6) Multidimensional Turing Machine6) Multidimensional Turing Machine
7) Composite Turing Machine7) Composite Turing Machine
8) Universal Turing Machine8) Universal Turing Machine
Types of Turing Machine

4. Dept. of Computer Science & IT, FUUAST
Theory of Computation
4
Turing MachineTuring Machine
Formal Definition

5. Dept. of Computer Science & IT, FUUAST
Theory of Computation
5
Turing MachineTuring Machine

6. Dept. of Computer Science & IT, FUUAST
Theory of Computation
6
Turing MachineTuring Machine
1.Start in state q
0
2.Read symbol under head
3.Write new symbol
4.Shift left/right
5.Enter new state q
j
Steps

7. Dept. of Computer Science & IT, FUUAST
Theory of Computation
7
Turing MachineTuring Machine
Notational Conventions For Turing Machines

8. Dept. of Computer Science & IT, FUUAST
Theory of Computation
8
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

9. Dept. of Computer Science & IT, FUUAST
Theory of Computation
9
Turing MachineTuring Machine
Moves for input 0011:
Moves for input 0010:

10. Dept. of Computer Science & IT, FUUAST
Theory of Computation
10
Turing MachineTuring Machine
Transition Diagram for 0011 input

11. Dept. of Computer Science & IT, FUUAST
Theory of Computation
11
Pushdown AutomataPushdown Automata
A Turing Machine M computes a function ( proper subtraction) for
0
m
10
n
on the tape.
means if m ≥ n then m - n else if m < n then 0

12. Dept. of Computer Science & IT, FUUAST
Theory of Computation
12
Turing MachineTuring Machine
Evaluating function

13. Dept. of Computer Science & IT, FUUAST
Theory of Computation
13
Turing MachineTuring Machine
Evaluating function

14. Dept. of Computer Science & IT, FUUAST
Theory of Computation
14
Turing MachineTuring Machine
Transition Table for the function

15. Dept. of Computer Science & IT, FUUAST
Theory of Computation
15
Turing MachineTuring Machine
Transition Diagram for

16. Dept. of Computer Science & IT, FUUAST
Theory of Computation
16
Turing MachineTuring Machine
Transition Table for the function
Transition Diagram for

17. Dept. of Computer Science & IT, FUUAST
Theory of Computation
17
0 0 1 1 B B
q
0
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }
Turing MachineTuring Machine

18. Dept. of Computer Science & IT, FUUAST
Theory of Computation
18
X 0 1 1 B B
q
1
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

19. Dept. of Computer Science & IT, FUUAST
Theory of Computation
19
X 0 1 1 B B
q
1
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

20. Dept. of Computer Science & IT, FUUAST
Theory of Computation
20
X 0 Y 1 B B
q
2
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

21. Dept. of Computer Science & IT, FUUAST
Theory of Computation
21
X 0 Y 1 B B
q
2
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

22. Dept. of Computer Science & IT, FUUAST
Theory of Computation
22
X 0 Y 1 B B
q
0
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

23. Dept. of Computer Science & IT, FUUAST
Theory of Computation
23
X 0 Y 1 B B
q
0
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

24. Dept. of Computer Science & IT, FUUAST
Theory of Computation
24
X X Y 1 B B
q
1
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

25. Dept. of Computer Science & IT, FUUAST
Theory of Computation
25
X X Y 1 B B
q
1
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

26. Dept. of Computer Science & IT, FUUAST
Theory of Computation
26
X X Y Y B B
q
2
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

27. Dept. of Computer Science & IT, FUUAST
Theory of Computation
27
X X Y Y B B
q
2
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

28. Dept. of Computer Science & IT, FUUAST
Theory of Computation
28
X X Y Y B B
q
0
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

29. Dept. of Computer Science & IT, FUUAST
Theory of Computation
29
X X Y Y B B
q
0
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

30. Dept. of Computer Science & IT, FUUAST
Theory of Computation
30
X X Y Y B B
q
3
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

31. Dept. of Computer Science & IT, FUUAST
Theory of Computation
31
X X Y Y B B
q
3
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

32. Dept. of Computer Science & IT, FUUAST
Theory of Computation
32
X X Y Y B B
q
4
Turing MachineTuring Machine
A Turing Machine M that accepts the language { 0
n
1
n
| n ≥0 }

33. End of Simulation
Dept. of Computer Science & IT, FUUAST
Theory of Computation
33
Turing MachineTuring Machine

34. Dept. of Computer Science & IT, FUUAST
Theory of Computation
34
Evaluating function
0 0 0 0 0 1 0 0 0 B B
q
0
Turing MachineTuring Machine

35. Dept. of Computer Science & IT, FUUAST
Theory of Computation
35
Evaluating function
B 0 0 0 0 1 0 0 0 B B
q
1
Turing MachineTuring Machine

36. Dept. of Computer Science & IT, FUUAST
Theory of Computation
36
Evaluating function
B 0 0 0 0 1 0 0 0 B B
q
1
Turing MachineTuring Machine

37. Dept. of Computer Science & IT, FUUAST
Theory of Computation
37
Evaluating function
B 0 0 0 0 1 0 0 0 B B
q
1
Turing MachineTuring Machine

38. Dept. of Computer Science & IT, FUUAST
Theory of Computation
38
Evaluating function
B 0 0 0 0 1 0 0 0 B B
q
1
Turing MachineTuring Machine

39. Dept. of Computer Science & IT, FUUAST
Theory of Computation
39
Evaluating function
B 0 0 0 0 1 0 0 0 B B
q
1
Turing MachineTuring Machine

40. Dept. of Computer Science & IT, FUUAST
Theory of Computation
40
Evaluating function
B 0 0 0 0 1 0 0 0 B B
q
2
Turing MachineTuring Machine

41. Dept. of Computer Science & IT, FUUAST
Theory of Computation
41
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
3
Turing MachineTuring Machine

42. Dept. of Computer Science & IT, FUUAST
Theory of Computation
42
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
3
Turing MachineTuring Machine

43. Dept. of Computer Science & IT, FUUAST
Theory of Computation
43
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
3
Turing MachineTuring Machine

44. Dept. of Computer Science & IT, FUUAST
Theory of Computation
44
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
3
Turing MachineTuring Machine

45. Dept. of Computer Science & IT, FUUAST
Theory of Computation
45
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
3
Turing MachineTuring Machine

46. Dept. of Computer Science & IT, FUUAST
Theory of Computation
46
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
3
Turing MachineTuring Machine

47. Dept. of Computer Science & IT, FUUAST
Theory of Computation
47
Evaluating function
B 0 0 0 0 1 1 0 0 B B
q
0
Turing MachineTuring Machine

48. Dept. of Computer Science & IT, FUUAST
Theory of Computation
48
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
1
Turing MachineTuring Machine

49. Dept. of Computer Science & IT, FUUAST
Theory of Computation
49
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
1
Turing MachineTuring Machine

50. Dept. of Computer Science & IT, FUUAST
Theory of Computation
50
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
1
Turing MachineTuring Machine

51. Dept. of Computer Science & IT, FUUAST
Theory of Computation
51
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
1
Turing MachineTuring Machine

52. Dept. of Computer Science & IT, FUUAST
Theory of Computation
52
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
2
Turing MachineTuring Machine

53. Dept. of Computer Science & IT, FUUAST
Theory of Computation
53
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
2
Turing MachineTuring Machine

54. Dept. of Computer Science & IT, FUUAST
Theory of Computation
54
Evaluating function
B B 0 0 0 1 1 0 0 B B
q
2
Turing MachineTuring Machine

55. Dept. of Computer Science & IT, FUUAST
Theory of Computation
55
Evaluating function
B B 0 0 0 1 1 1 0 B B
q
3
Turing MachineTuring Machine

56. Dept. of Computer Science & IT, FUUAST
Theory of Computation
56
Evaluating function
B B 0 0 0 1 1 1 0 B B
q
3
Turing MachineTuring Machine

57. Dept. of Computer Science & IT, FUUAST
Theory of Computation
57
Evaluating function
B B 0 0 0 1 1 1 0 B B
q
3
Turing MachineTuring Machine

58. Dept. of Computer Science & IT, FUUAST
Theory of Computation
58
Evaluating function
B B 0 0 0 1 1 1 0 B B
q
3
Turing MachineTuring Machine

59. Dept. of Computer Science & IT, FUUAST
Theory of Computation
59
Evaluating function
B B 0 0 0 1 1 1 0 B B
q
3
Turing MachineTuring Machine

60. Dept. of Computer Science & IT, FUUAST
Theory of Computation
60
Evaluating function
B B 0 0 0 1 1 1 0 B B
q
0
Turing MachineTuring Machine

61. Dept. of Computer Science & IT, FUUAST
Theory of Computation
61
Evaluating function
B B B 0 0 1 1 1 0 B B
q
1
Turing MachineTuring Machine

62. Dept. of Computer Science & IT, FUUAST
Theory of Computation
62
Evaluating function
B B B 0 0 1 1 1 0 B B
q
1
Turing MachineTuring Machine

63. Dept. of Computer Science & IT, FUUAST
Theory of Computation
63
Evaluating function
B B B 0 0 1 1 1 0 B B
q
1
Turing MachineTuring Machine

64. Dept. of Computer Science & IT, FUUAST
Theory of Computation
64
Evaluating function
B B B 0 0 1 1 1 0 B B
q
2
Turing MachineTuring Machine

65. Dept. of Computer Science & IT, FUUAST
Theory of Computation
65
Evaluating function
B B B 0 0 1 1 1 0 B B
q
2
Turing MachineTuring Machine

66. Dept. of Computer Science & IT, FUUAST
Theory of Computation
66
Evaluating function
B B B 0 0 1 1 1 0 B B
q
2
Turing MachineTuring Machine

67. Dept. of Computer Science & IT, FUUAST
Theory of Computation
67
Evaluating function
B B B 0 0 1 1 1 1 B B
q
3
Turing MachineTuring Machine

68. Dept. of Computer Science & IT, FUUAST
Theory of Computation
68
Evaluating function
B B B 0 0 1 1 1 1 B B
q
3
Turing MachineTuring Machine

69. Dept. of Computer Science & IT, FUUAST
Theory of Computation
69
Evaluating function
B B B 0 0 1 1 1 1 B B
q
3
Turing MachineTuring Machine

70. Dept. of Computer Science & IT, FUUAST
Theory of Computation
70
Evaluating function
B B B 0 0 1 1 1 1 B B
q
3
Turing MachineTuring Machine

71. Dept. of Computer Science & IT, FUUAST
Theory of Computation
71
Evaluating function
B B B 0 0 1 1 1 1 B B
q
3
Turing MachineTuring Machine

72. Dept. of Computer Science & IT, FUUAST
Theory of Computation
72
Evaluating function
B B B 0 0 1 1 1 1 B B
q
3
Turing MachineTuring Machine

73. Dept. of Computer Science & IT, FUUAST
Theory of Computation
73
Evaluating function
B B B 0 0 1 1 1 1 B B
q
0
Turing MachineTuring Machine

74. Dept. of Computer Science & IT, FUUAST
Theory of Computation
74
Evaluating function
B B B B 0 1 1 1 1 B B
q
1
Turing MachineTuring Machine

75. Dept. of Computer Science & IT, FUUAST
Theory of Computation
75
Evaluating function
B B B B 0 1 1 1 1 B B
q
1
Turing MachineTuring Machine

76. Dept. of Computer Science & IT, FUUAST
Theory of Computation
76
Evaluating function
B B B B 0 1 1 1 1 B B
q
2
Turing MachineTuring Machine

77. Dept. of Computer Science & IT, FUUAST
Theory of Computation
77
Evaluating function
B B B B 0 1 1 1 1 B B
q
2
Turing MachineTuring Machine

78. Dept. of Computer Science & IT, FUUAST
Theory of Computation
78
Evaluating function
B B B B 0 1 1 1 1 B B
q
2
Turing MachineTuring Machine

79. Dept. of Computer Science & IT, FUUAST
Theory of Computation
79
Evaluating function
B B B B 0 1 1 1 1 B B
q
2
Turing MachineTuring Machine

80. Dept. of Computer Science & IT, FUUAST
Theory of Computation
80
Evaluating function
B B B B 0 1 1 1 1 B B
q
4
Turing MachineTuring Machine

81. Dept. of Computer Science & IT, FUUAST
Theory of Computation
81
Evaluating function
B B B B 0 1 1 1 B B B
q
4
Turing MachineTuring Machine

82. Dept. of Computer Science & IT, FUUAST
Theory of Computation
82
Evaluating function
B B B B 0 1 1 B B B B
q
4
Turing MachineTuring Machine

83. Dept. of Computer Science & IT, FUUAST
Theory of Computation
83
Evaluating function
B B B B 0 1 B B B B B
q
4
Turing MachineTuring Machine

84. Dept. of Computer Science & IT, FUUAST
Theory of Computation
84
Evaluating function
B B B B 0 B B B B B B
q
4
Turing MachineTuring Machine

85. Dept. of Computer Science & IT, FUUAST
Theory of Computation
85
Evaluating function
B B B B 0 B B B B B B
q
4
Turing MachineTuring Machine

86. Dept. of Computer Science & IT, FUUAST
Theory of Computation
86
Evaluating function
B B B 0 0 B B B B B B
q
6
Turing MachineTuring Machine
Final State

87. Dept. of Computer Science & IT, FUUAST
Theory of Computation
87
End of Simulation
Turing MachineTuring Machine

88. Dept. of Computer Science & IT, FUUAST
Theory of Computation
88
Turing MachineTuring Machine
0
m
10
n
1
Multiplication

89. Dept. of Computer Science & IT, FUUAST
Theory of Computation
89
Turing MachineTuring Machine
0
m
10
n
1
Multiplication

90. Dept. of Computer Science & IT, FUUAST
Theory of Computation
90
Turing MachineTuring Machine

91. Dept. of Computer Science & IT, FUUAST
Theory of Computation
91
Turing MachineTuring Machine

92. Dept. of Computer Science & IT, FUUAST
Theory of Computation
92
Turing MachineTuring Machine

93. Dept. of Computer Science & IT, FUUAST
Theory of Computation
93
Turing MachineTuring Machine

94. Dept. of Computer Science & IT, FUUAST
Theory of Computation
94
Turing MachineTuring Machine
Variants of Turing Machine
A normal TM is a 7-tuple
(Q, Σ, G, δ, q
0
, q
accept
, q
reject
) where:
everything is the same as a TM except the
transition function:
δ: Q x G
k
→ Q x G
k
x {L, R}
k
δ(q
i
, a
1
,a
2
,…,a
k
) = (q
j
, b
1
,b
2
,…,b
k
, L, R,…, L) =
“in state q
i
, reading a
1
,a
2
,…,a
k
on k tapes, move to
state q
j
, write b
1
,b
2
,…,b
k
on k tapes, move L, R on
k tapes as specified.”
oMultitape Turing Machine:

95. Dept. of Computer Science & IT, FUUAST
Theory of Computation
95
Turing MachineTuring Machine
k-tape TM
011001110100
q
0
input tape
finite control
…
k read/write
heads
011001
“work tapes”
…
011001110100 …
0 …
…

96. Dept. of Computer Science & IT, FUUAST
Theory of Computation
96
Turing MachineTuring Machine
Informal description of k-tape TM:
 Input written on left-most squares of tape #1
 Rest of squares are blank on all tapes
 At each point, take a step determined by
•current k symbols being read on k tapes
•current state of finite control
 A step consists of
•writing k new symbols on k tapes
•moving each of k read/write heads left or right
•changing state

97. Dept. of Computer Science & IT, FUUAST
Theory of Computation
97
Turing MachineTuring Machine
Theorem: Every k-tape TM has an equivalent single-tape TM.
Proof: Simulate k-tape TM on a 1-tape TM.
. . . abab
aa
bbcd
. . .
. . .
(input tape)
#abab#aa#bbcd#. . .
• add new symbol x for
each old x
•marks location of “virtual
heads”

98. Dept. of Computer Science & IT, FUUAST
Theory of Computation
98
Turing MachineTuring Machine
Theorem:
The time taken by the one-tape TM to
simulate n moves of the k-tape TM is
O(n
2
).

99. Dept. of Computer Science & IT, FUUAST
Theory of Computation
99
Turing MachineTuring Machine
oNondeterministic Turing Machine (NTM):
A nondeterministic Turing Machine (NTM) differs from the
deterministic variety by having a transition function δ such that
for each state q and tape symbol X, δ(q, X) is a set of triples
{(q
1
,Y
1
,D
1
), (q
2
,Y
2
,D
2
), ……….. (q
k
,Y
k
,D
k
)}
Where k is any finite integer. The NTM can choose, at each step,
any of the triples to be the next move. It cannot, however, pick a
state from one, a tape symbol from another, a the direction from
yet another.

100. Dept. of Computer Science & IT, FUUAST
Theory of Computation
100
Turing MachineTuring Machine
Theorem: Every NTM has an equivalent (deterministic) TM.
Proof: Simulate NTM with a deterministic TM
C
start
• computations of M are a tree
• nodes are configurations
• fanout is b = maximum number of
choices in transition function
• leaves are accept/reject
configurations.
accrej

101. Dept. of Computer Science & IT, FUUAST
Theory of Computation
101
Turing MachineTuring Machine
Simulating NTM M with a deterministic TM:
Breadth-first search of tree
•if M accepts: we will encounter accepting leaf and
accept
•if M rejects: we will encounter all rejecting leaves,
finish traversal of tree, and reject
•if M does not halt on some branch: we will not halt
as that branch is infinite…

102. Dept. of Computer Science & IT, FUUAST
Theory of Computation
102
Turing MachineTuring Machine
Simulating NTM M with a deterministic TM:
ouse a 3 tape TM:
•tape 1: input tape (read-only)
•tape 2: simulation tape (copy of M’s tape at point
corresponding to some node in the tree)
•tape 3: which node of the tree we are exploring (string
in {1,2,…b}*)
oInitially, tape 1 has input, others blank

103. Dept. of Computer Science & IT, FUUAST
Theory of Computation
103
Turing MachineTuring Machine

104. Dept. of Computer Science & IT, FUUAST
Theory of Computation
104
Turing MachineTuring Machine
Turing Machine and Computer
oA computer can simulate Turing Machine.
oA Turing Machine can simulate a computer.

105. Dept. of Computer Science & IT, FUUAST
Theory of Computation
105
Turing MachineTuring Machine
Simulating a Turing Machine by Computer

106. Dept. of Computer Science & IT, FUUAST
Theory of Computation
106
Turing MachineTuring Machine
Simulating a Computer by Turing Machine
Both addresses and
contents are written in
binary. The marker
symbol * and # are
used to find the ends
of addresses and
contents. Another
marker,$, indicates
the beginning of the
sequence of
addresses and
contents
Both addresses and
contents are written in
binary. The marker
symbol * and # are
used to find the ends
of addresses and
contents. Another
marker,$, indicates
the beginning of the
sequence of
addresses and
contents

107. Dept. of Computer Science & IT, FUUAST
Theory of Computation
107
Turing MachineTuring Machine
A universal Turing machine is a Turing machine T
u
that
works as follows. It is assumed to receive an input string
of the form e(T )e(z), where T is an arbitrary TM, z is a
string over the input alphabet of T , and e is an encoding
function whose values are strings in {0, 1} . The
∗
computation performed by T
u
on this input string satisfies
these two properties:
1. T
u
accepts the string e(T )e(z) if and only if T accepts z.
2. If T accepts z and produces output y, then T
u
produces
output e(y).
Universal Turing Machine

108. Dept. of Computer Science & IT, FUUAST
Theory of Computation
108
Turing MachineTuring Machine
Universal Turing Machine

109. Dept. of Computer Science & IT, FUUAST
Theory of Computation
109
Turing MachineTuring Machine
END