L21,L22 Turing Machines

Lec 20,21 : Computation Theory Turing Machines & their examples
1
Turing Machines: (TM)
Turing machine is a simple mathematical model of a
computer. Turning machine models the computing capability of
a general- purpose computer. This model will enable us not only
to study some theoretical limitations on the tasks that computers
can perform, it will also be a model that we can use to show that
certain operations "can" be done by computer.
The languages accepted by F.A. are called "regular" and
they can be defined by regular expression. The languages
accepted by PDA are called CFGs. The languages accepted by
TM are called type ?, or phrase-structure or recursively
enumerable language.
a1 a2 … ai … an B B …
The figure above is basic Turing machine, has a finite
control, an input tape that is divided into cells, and a tape head
that scan one cell of the tape at a time. The tape has a leftmost
cell bat is infinite to the right. Each cell of the tape may hold
exactly one symbol. Initially, the n leftmost cells hold the input.
The remaining infinity of cells each hold the blank.
In one move the Turing machine, depending upon the symbol
scanned by the tape head and the state of the finite control,
1- changes state,
2- prints a symbol on the tape cell scanned, replacing what was
written there, and
Lec 20,21 : Computation Theory Turing Machines & their examples
2
3- moves its head left or right one cell
Note that the difference between a Turing machine and a twoway
finite automation lies in the ability to change symbols on its
tape.
Formally, a Turing machine (TM) is denoted:
M ? (Q,?,?, t,q? ,B,F)
Where
Q is the finite set of "states",
? is the finite set of a allowable "tape symbols",
B, a symbol of ? , is the "blank",
? , a subset of ? not including B, is the set of "input symbols"
T, is the next move function, a mapping from Q?? to
Q???{L,R},
q? , in Q is the "start state ",
F ? Q is the set of "final states", or called "HALT states" that
cause execution to terminate when we enter them.
The "language accepted" by M, denoted L(M), is the set of those
word in * ? that cause M to enter a final state.
Lec 20,21 : Computation Theory Turing Machines & their examples
3
First Example TM
L={0n1n}
({ , , , , },{0,1, },{ , },{ }) 1 2 3 4 4
Q F
M q q q q q B x y q
? ?
? ? and Transition functions are:
( ,0) ( , , ) 1 t q ? q X R ? ( ,0) ( ,0, ) 2 3 t q ? q L
( , ) ( , , ) 1 1 t q Y ? q Y R ( , ) ( , , ) 2 4 t q X ? q X R
( ,0) ( ,0, ) 1 1 t q ? q R ( , ) ( , , ) 2 2 t q Y ? q Y L
( ,1) ( , , ) 1 2 t q ? q Y L ( ,0) ( ,0, ) 3 3 t q ? q L
( , ) ( , , ) 3 0 t q x ? q x R ( , ) ( , , ) 4 4 t q Y ? q Y R
( , ) ( , , ) 4 5 t q B ? q B R
A computation of M on input 0011 is:
0011? 011? 0 11? 0 1? 1 1 2 q Xq X q Xq Y ?
0 1? 0 1? 1? 1? 3 1 1 q X Y Xq Y XXq Y XXXq ?
y\y,L
0\0,L
q0 0\x,R 1\y,L
q0
q1 q2
x\x,R
B\B,R
q4 q5
0\0,R
y\y,R
y\y,R
0\0,L
x\x,R
q3
Lec 20,21 : Computation Theory Turing Machines & their examples
4
Second Example TM
L= {WWr W={a,b}+}
XXq YY?Xq XYY?XXq XY?XXYq Y ? 2 2 4 4
4 5 XXYYq ?XXYYBq
q0
q0
q1 q2
q4
q3
q5 q6
q7
a\B,R
a\a,R
b\b,R
B\B,L a\B,L
a\a,L
b\b,L
B\B,R
B\B,R
a\a,R
b\b,R
B\B,L
b\B,R
b\B,L
a\a,L
b\b,L
B\B,R