Chapter 19: Turing Machines
Topics
Introduction
Definition of Turing Machine
Turing machine transition diagrams
A TM that accepts anbn
Introduction
-
the Turing machine is yet another machine model of computation
-
"Church’s Thesis" hypothesizes that:
-
anything that can be computed at all
-
can be computed by a Turing machine
Definition
of Turing machine
1. An finite alphabet S and a blank
symbol D (not in S
)
2. A tape, with cells 1, 2, …
-
each cell can hold one (alphabet or blank) character
-
initially, the tape holds an input string from S
-
with the rest of the cells blank
3. A tape head (initially positioned at cell 1) which can:
-
read the current cell
-
replace it with (write) another character
-
move one position to the right or left
Notes:
machine crashes if head moves to the left of cell 1
writing a blank is called erasing
4. An alphabet G of symbols that the
tape head can write
-
needs not be disjoint from S
5. A finite set of states, including
-
exactly one start state (machine starts in this state)
-
0 or more halt states (these are accepting states)
6. A set of program rules, which are quintuples of the form:
(state, read-letter, write-letter, direction, new-state)
-
e.g. (5, a, b, L, 6) means:
-
if the machine is in state 5, and reads an "a" from the current cell, it
will write a "b" in the current cell, move the head to the Left, and enter
state 6.
A Turing machine is deterministic:
-
for a given state and read-input
-
there is only one quintuple in the set of program rules
The machine accepts its input if it enters a halt state.
Turing
machine transition diagrams
We will depict our machines as transition diagrams, e.g.:
Interpretation:
-
if the machine is in state 1 and reads an a
-
it will write an a, move the head to the right, and move to state
2
-
this represents the program quintuple (1,a,a,R,2)
-
for this representation, transitions will be labeled with triples
What language does this TM accept?
Is there a simpler one that accepts the same language?
A
TM that accepts anbn
This machine is found on p. 439 of our text, Introduction to Computer
Theory (2nd Edition), by Daniel Cohen, John Wiley &
Sons, 1997.
Let’s see what happens with input aabb:
| S |
tape |
comment |
| 1 |
aabb |
"eliminate" (by writing over) the leftmost a |
| 2 |
Aabb |
look for matching b |
| 2 |
Aabb |
found it |
| 3 |
AaBb |
eliminate it; move left to look for leftmost
a |
| 4 |
AaBb |
found rightmost A; leftmost a is just to right |
| 1 |
AaBb |
this is the leftmost a; eliminate it |
| 2 |
AABb |
look for matching b |
| 2 |
AABb |
found it; eliminate it |
| 3 |
AABB |
move left to look for another a |
| 3 |
AABB |
none found |
| 5 |
AABB |
make sure nothing to the right of last B |
| 5 |
AABB |
|
| 5 |
AABBD |
nothing there; HALT (accept) |