Introduction to Turing Machines

1
 Automata
A Finite Automaton has only its states to serve as memory - very
limited in what languages it could recognize

DTM, NTM

LBA
PDA
DPDA
DFA,
NFA

2
 The Turing Machine
 Alan Mathison Turing (b. 1912, d. 1954) Contributed
much to the foundations of computing theory.
 Published the Turing machine model in 1937.

 Church-Turing Thesis - “Any algorithmic procedure that

can be carried out by a human, a team of humans, or a
machine can be carried out by some Turing machine.”
– Unproveable, because we don’t have a precise definition of what
“algorithmic procedure” means, but generally accepted as true.
 Puts a limit on what can be computed.

3
 The Church-Turing Thesis

No model of digital computation is more powerful than a

Turing machine.

By “more powerful,” we mean “can recognize languages

that a TM cannot recognize.”

This is not something that can be proved. But everybody

believes it because no one has been able to devise a more
powerful model of computation.
4
 Definition: Turing Machine
A Turing machine (TM) is a 7-Tuple
T = (Q, , q0, , F),where
Q = a finite set of states
a finite set of symbols constituting theinput alphabet;
 – {}
= a finite set of symbols constituting thetape alphabet
the transition function: Q    Q    {L, R}
q0 = the start state (q0  Q)
 is a special symbol, the blank symbol
F  Q is the set of final states
5
 Definition: Turing Machine
Turing machines can be thought of as a finite
state automaton with slightly different labels
on the arcs, plus a tape as auxiliary memory,
and a tape head (or read-write head).

No boundaries -- infinite length

Tape
...... ......

6
Read-Write head
 Definition: Turing Machine
The tape on a Turing machine can be thought of as a
linear structure marked off into squares or cells. It is
usually defined as infinite in both directions, but may
be thought of as bounded on the left side, but infinite
on the right.
Each cell on the tape on a Turing machine can hold a
symbol from the input alphabet, a symbol from the
tape alphabet (which may include some symbols
which are not in the input alphabet), or a blank
symbol  which is distinct from the input alphabet.
7
 Standard Turing Machine
The standard Turing machine described by our textbook
has several features:
The TM has a tape that is unbounded in both directions.
The TM is deterministic in the sense that  defines at
most one move per configuration
There is no special input file; the input is copied onto
the tape.
There is no special output device; the tape contains the
output, if any.
8
 The TM tape head

The Turing machine has a tape head which reads

from and writes to the tape during each move.

The tape head can move right or left, or may stay

in the same position.

The tape head can read a character from the cell

under which it is positioned, or it may write a
character to the cell.
9
 The TM transition function
The TM transition function has the following
form:
(q, X) = (r, Y, D)
This says that when the TM is in state q, and the
read-write head reads a certain symbol (X) off the
tape, then the TM will change state to state r, write
a Y onto the tape, and move in direction D.
For example, (q1, b) = (q2, , R) means: “We are
currently in state q1; read the cell; it’s a b. OK, 10
 The TM transition function
•Wecan label the arcs(edges) of a finite state
machine to indicate the moves of the TM:

 / , R
q0 q1

 a b a   

11
 Processing a string

To process a string, we place the string onto the

tape, where it can be read by the read-write head,
surrounded by blank symbols on the left and right
ends of the input. Once the string is on the tape,
then processing can begin. We don’t need a
separate input string after that.

12
 Accepting a string
There is only one way that a string may be
accepted by a TM: If a move causes the machine
to move into an accepting halt state, then we stop
and accept the string. (There are no moves out of a
halt state.)
This may occur even when we haven’t finished
processing the whole string yet.
For example, if our TM is processing all the strings
that have aabb in them somewhere, the TM may
halt after processing the 6th character of this string:
13
 Accepting a string
If T = (Q, , q0, , F) is a Turing machine,
and w  +, w is accepted by T if, starting in the
initial configuration corresponding to input w, T
eventually enters a final acceptance state and halts.
In other words, w is accepted if there exists y and z
* so that
q0w |-T* yqfz, for some qf F
In this situation, we say that T halts on input w.
The language accepted by T is the set L(T) of input
strings on which T halts.
14
 Crashing and Halting
There are 2 ways a string may fail to be accepted by a TM:
1. Crashing
a. If a symbol is found on the tape for which the transition
function is undefined, and the current state is not the
accepting halt state, then we crash.
b. If our TM has a bounded left end, and a move is specified
which causes the machine to move off of the left end of the
tape, then we crash.
2. Looping
a. If an input string causes the TM to enter an infinite loop,
then we loop forever.
If the TM crashes, the string is explicitly rejected.
15
 Exercises
Design a TM that accepts L = {anbn | n  1}
To do this, we can construct the transition
table for the TM. We can use a matrix as a
short-hand representation:

16
 {anbn | n  1}

a b x y Δ

q0 q1,x,R q3,y,R

q1 q1,a,R q2,y,L q1,y,R

q2 q2,a,L q0,x,R q2,y,L

q3 q3,y,R q4,Δ,R

q4
17
 {anbn | n  1}
 Replace leftmost a with an x and find the first b and
replace with a y:
(q0,a)=(q1,x,R) (q1,y)=(q1,y,R)
(q1,a)=(q1,a,R) (q1,b)=(q2,y,L)
 Come back to the next left-most a:
(q2,y)=(q2,y,L) (q2,x)=(q0,x,R)
(q2,a)=(q2,a,L)
 Finally, check to see if all input has been processed and the
a’s and b’s balance (and a’s precede the b’s):
(q0,y)= (q3,y,R) (q3, Δ) = (q4, Δ,R)
(q3,y) = (q3,y,R)
18
 Example #1: {0n1n | n >= 1}

0 1 X Y B
q0 (q1, X, R) - - (q3, Y, R) -
q1 (q1, 0, R) (q2, Y, L) - (q1, Y, R) -
q2 (q2, 0, L) - (q0, X, R) (q2, Y, L) -
q3 - - - (q3, Y, R) (q4, B, R)
q4 - - - - -


 Sample Computation: (on 0011)

q00011 |— Xq1011
|— X0q111
|— Xq20Y1
|— q2X0Y1
|— Xq00Y1
|— XXq1Y1
|— XXYq11
|— XXq2YY
|— Xq2XYY
|— XXq0YY
|— XXYq3Y
|— XXYYq3
|— XXYYBq4 19
Transition Diagram

20
 Exercises
Consider the processing of the string w = aaabbb
Is this string accepted by the TM?
Consider the processing of the string w = aaabb.
Is this string accepted by the TM?
How does the TM reject the string?

21
 Exercises
 Recall that the following languages are not
context-free.
– {anbncn | n  0}
– {ww | w  {a,b}*}
 In English, describe how a Turing machine
could accept each of these languages
 Try to draw the transition diagrams for the
Turing machines
22
 {anbncn | n  1}
a b c x y z Δ

q0 q1xR q4yR

q1 q1aR q2yR q1yR

q2 q2bR q3zL q2zR

q3 q3aL q3bL q0xR q3yL q3zL

q4 q4yR q4zR q5ΔR

q5
23
 Design TM to calculate m – n, where m, n are
positive integer and m > n.
f(m,n) = m – n
Suppose m is 5 and n is 3 then we can represent m by 5 0’s and n by 3 0’s. Both m and n are separated
by1.
5–3=2
000001000 = 00
The transition’s for this TM is as below –
δ(q0 , 0) = (q1 , β, R)
δ(q1 , 0) = (q1 , 0, R)
δ(q1 , 1) = (q2 , 1, R)
δ(q2 , 0) = (q2 , 0, R)
δ(q2 , β) = (q3 , β, L)
δ(q3 , 0) = (q4 , β, L) // when all 0’s are over at q3 , it receive 1 at end.
δ(q4 , 0) = (q4 , 0, L)
δ(q4 , 1) = (q5 , 1, L)
δ(q5 , 0) = (q5 , 0, L)
δ(q5 , β) = (q6 , β, R)
δ(q6 , 0) = (q1 , β, R) // See Note 1 24
δ(q3 , 1) = (qf , 0, L)
Note1: Beginning of next cycle for cancellation of 0 by 0. This process continues till all 0’s in n are
cancelled by an equal no of 0’s in m. In the next cycle a 0 is cancelled in m but n has no more 0’s so
read/write head receives the separator 1 in q 3 state and replace it with 0 and enters in final state q f.

25
 Design TM to calculate m + n, where m, n are positive
integer
f(m,n) = m + n

Here suppose m is 3 and n is 4 then we can represent m by 3 1’s and n by 4

1’s. Both m and n are separated by 0.
3+4=7
11101111 = 1111111
The transition’s for this TM is as below –
Logic: When 0 is encountered, it is changed to 1 and last 1 is replaced by β.
δ(q0 , 1) = (q0 , 1, R)
δ(q0 , 1) = (q1 , 1, R)
δ(q1 , 1) = (q1 , 1, R)
δ(q1 , β ) = (q2 , β, L)
δ(q2 , 1) = (qf , β, L)

26
Thank You

27