Introduction To Turing Machine
President University
1
Models of computing
DFA - regular languages
Push down automata - Context-free
Bounded Turing M’s - Context sensitive
Turing machines - Phrase-structure
2
Foundations
The theory of computation
and the practical
application it made possible
— the computer — was
developed by an
Englishman called Alan
Turing.
3
The Turing Machine
(4) At any time, the machine is in one
Turing’s machine — which came to be
of a finite number of internal
called the Turing machine — was this:
states.
(1) A tape of infinite length
(5) The machine has instructions that
(2) Finitely many squares of determine what it does given its
the tape have a single internal state and the symbol it
symbol from a finite encounters on the tape. It can
language. – change its internal state;
(3) Someone (or something) – change the symbol on the
that can read the squares square;
and write in them.
– move forward;
– move backward;
– halt (i.e. stop).
6
Current state = 10
If current state = 1
and current symbol = 0
then new state = 10
new symbol = 1
move right
1
0
1
1
7
Current state = 10
If current state = 1
and current symbol = 0
then new state = 10
new symbol = 1
move right
1
1
1
1
8
Current state = 10
If current state = 1
and current symbol = 0
then new state = 10
new symbol = 1
move right
1
1
1
1
9
Functions
It is essential to the idea of a Turing machine that it is not a physical
machine, but an abstract one — a set of procedures.
It makes no difference whether the machine is embodied by a person in a
boxcar on a track, or a person with a paper and pencil, or
a smart and well-trained flamingo.
10
First computers: custom computing machines
Input tape (read only)
Control
Work tape (memory)
1950 -- Eniac: the control
is hardwired manually for Output tape (write only)
each problem.
1940: VON NEUMANN:
DISTINCTION BETWEEN DATA AND INSTRUCTIONS 12
Can Machines Think?
In “Computing machinery and intelligence,” written
in 1950, Turing asks whether machines can think.
He claims that this question is too vague, and
proposes, instead, to replace it with a different one.
That question is: Can machines pass the “imitation
game” (now called the Turing test)? If they can, they
are intelligent.
Turing is thus the first to have offered a rigorous test
for the determination of intelligence quite generally.
13
The Turing Test
The game runs as follows. You sit at a computer terminal and have an
electronic conversation. You don’t know who is on the other end; it could
be a person or a computer responding as it has been programmed to do.
If you can’t distinguish between a human being and a computer from
your interactions, then the computer is intelligent.
Note that this is meant to be a sufficient condition of intelligence only.
There may be other ways to be intelligent.
14
The Church-Turning Thesis
Turing, and a logician called
Alonzo Church (1903-1995),
independently developed the
idea (not yet proven by
widely accepted) that
whatever can be computed
by a mechanical procedure
can be computed by a
Turing machine.
This is known as the
Church-Turing thesis.
16
Turing Machines
18
The Language Hierarchy
n n n ?
a b c ww ?
Context-Free Languages
n n R
a b ww
Regular Languages
a* a *b *
19
Languages accepted by
Turing Machines
n n n
a b c ww
Context-Free Languages
n n R
a b ww
Regular Languages
a* a *b *
20
Tape A Turing Machine
...... ......
Read-Write head
Control Unit
21
The Tape
No boundaries -- infinite length
...... ......
Read-Write head
The head moves Left or Right
22
...... ......
Read-Write head
The head at each time step:
1. Reads a symbol
2. Writes a symbol
3. Moves Left or Right
23
Example:
Time 0
...... ......
a b a c
Time 1
...... ......
a b k c
1. Reads a
2. Writes k
3. Moves Left
24
Time 1
...... ......
a b k c
Time 2
...... ......
a f k c
1. Reads b
2. Writes f
3. Moves Right
25
The Input String
Input string Blank symbol
......
a b a c ......
head
Head starts at the leftmost position
of the input string
26
Input string Blank symbol
......
a b a c ......
head
Remark: the input string is never empty
27
States & Transitions
Read Write
Move Left
q1 a → b, L q2
Move Right
q1 a → b, R q2
28
Example:
Time 1
a b a c
...... ......
q1
current state
q1 a → b, R q2
29
Time 1
a b a c
...... ......
q1
Time 2
......
a b b c ......
q2
q1 a → b, R q2
31
Halting
The machine halts if there are
no possible transitions to follow
35
Example:
......
a b a c ......
q1
a → b, R q2
No possible transition
q1
HALT!!!
b → d, L q3
36
Final States
q1 q2 Allowed
q1 q2 Not Allowed
• Final states have no outgoing transitions
• In a final state the machine halts
37
Acceptance
If machine halts
Accept Input in a final state
If machine halts
in a non-final state
or
Reject Input If machine enters
an infinite loop
38
Turing Machine Example
A Turing machine that accepts the language:
aa *
a → a, R
→ , L
q0 q1
39
Time 0 a a a
q0
a → a, R
→ , L
q0 q1
40
Time 1 a a a
q0
a → a, R
→ , L
q0 q1
41
Time 2 a a a
q0
a → a, R
→ , L
q0 q1
42
Time 3 a a a
q0
a → a, R
→ , L
q0 q1
43
Time 4 a a a
q1
a → a, R Halt & Accept
→ , L
q0 q1
44
Rejection Example
Time 0 a b a
q0
a → a, R
→ , L
q0 q1
45
Time 1 a b a
q0
No possible Transition
a → a, R Halt & Reject
→ , L
q0 q1
46
Infinite Loop Example
b → b, L
a → a, R
→ , L
q0 q1
47
Time 0 a b a
q0
b → b, L
a → a, R
→ , L
q0 q1
48
Time 1 a b a
q0
b → b, L
a → a, R
→ , L
q0 q1
49
Time 2 a b a
q0
b → b, L
a → a, R
→ , L
q0 q1
50
Time 2 a b a
q0
a b a
Infinite loop
Time 3
q0
Time 4 a b a
q0
Time 5 a b a
q0
51
Because of the infinite loop:
•The final state cannot be reached
•The machine never halts
•The input is not accepted
52
Another Turing Machine Example
n n
Turing machine for the language {a b }
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
53
Time 0 a a b b
q0
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
54
Time 1 x a b b
q1
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
55
Time 2 x a b b
q1
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
56
Time 3 x a y b
q2
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
57
Time 4 x a y b
q2
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
58
Time 5 x a y b
q0
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
59
Time 6 x x y b
q1
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
60
Time 7 x x y b
q1
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
61
Time 8 x x y y
q2
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
62
Time 9 x x y y
q2
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
63
Time 10 x x y y
q0
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
64
Time 11 x x y y
q3
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
65
Time 12 x x y y
q3
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
66
Time 13 x x y y
q4
Halt & Accept
q4 y → y, R y → y, L
y → y, R a → a, R a → a, L
→ , L
y → y, R a → x, R b → y, L
q3 q0 q1 q2
x → x, R
67
Languages accepted by
Turing Machines
n n n
a b c ww
Context-Free Languages
n n R
a b ww
Regular Languages
a* a *b *
69
End of intro to
Languages (sets of strings),
Grammars,
Automata,
and
Turing Machines (= computation).
70
