PPT: Turing Machines | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


1
Turing Machines
Page 2


1
Turing Machines
2
Turing Machines are…
n Very powerful (abstract) machines that
could simulate any modern day
computer (although very, very slowly!)
n Why design such a machine?
n If a problem cannot be “solved” even using
a TM, then it implies that the problem is
undecidable
n Computability vs. Decidability
For every input,
answer YES or NO
Page 3


1
Turing Machines
2
Turing Machines are…
n Very powerful (abstract) machines that
could simulate any modern day
computer (although very, very slowly!)
n Why design such a machine?
n If a problem cannot be “solved” even using
a TM, then it implies that the problem is
undecidable
n Computability vs. Decidability
For every input,
answer YES or NO
3
A Turing Machine (TM)
n M = (Q, ?, G, d, q
0
,B,F)
BBBX
1
X
2
X
3
… X
i
… X
n
BB
…
…
Finite
control
Infinite tape with tape symbols
B: blank symbol (special symbol reserved to indicate data boundary)
Input & output tape symbols
Tape head
This is like
the CPU &
program
counter
Tape is the
memory
Page 4


1
Turing Machines
2
Turing Machines are…
n Very powerful (abstract) machines that
could simulate any modern day
computer (although very, very slowly!)
n Why design such a machine?
n If a problem cannot be “solved” even using
a TM, then it implies that the problem is
undecidable
n Computability vs. Decidability
For every input,
answer YES or NO
3
A Turing Machine (TM)
n M = (Q, ?, G, d, q
0
,B,F)
BBBX
1
X
2
X
3
… X
i
… X
n
BB
…
…
Finite
control
Infinite tape with tape symbols
B: blank symbol (special symbol reserved to indicate data boundary)
Input & output tape symbols
Tape head
This is like
the CPU &
program
counter
Tape is the
memory
4
Transition function
n One move (denoted by |---)
in a TM does the following:
n d(q,X) = (p,Y,D)
n q is the current state
n X is the current tape symbol pointed by
tape head
n State changes from q to p
n After the move:
n X is replaced with symbol Y
n If D=“L”, the tape head moves “left” by
one position.
Alternatively, if D=“R” the tape head
moves “right” by one position.
q p
X / Y ,D
You can also use:
è for R
ç for L
Page 5


1
Turing Machines
2
Turing Machines are…
n Very powerful (abstract) machines that
could simulate any modern day
computer (although very, very slowly!)
n Why design such a machine?
n If a problem cannot be “solved” even using
a TM, then it implies that the problem is
undecidable
n Computability vs. Decidability
For every input,
answer YES or NO
3
A Turing Machine (TM)
n M = (Q, ?, G, d, q
0
,B,F)
BBBX
1
X
2
X
3
… X
i
… X
n
BB
…
…
Finite
control
Infinite tape with tape symbols
B: blank symbol (special symbol reserved to indicate data boundary)
Input & output tape symbols
Tape head
This is like
the CPU &
program
counter
Tape is the
memory
4
Transition function
n One move (denoted by |---)
in a TM does the following:
n d(q,X) = (p,Y,D)
n q is the current state
n X is the current tape symbol pointed by
tape head
n State changes from q to p
n After the move:
n X is replaced with symbol Y
n If D=“L”, the tape head moves “left” by
one position.
Alternatively, if D=“R” the tape head
moves “right” by one position.
q p
X / Y ,D
You can also use:
è for R
ç for L
5
ID of a TM
n Instantaneous Description or ID :
n X
1
X
2
…X
i-1
qX
i
X
i+1
…X
n
means:
n q is the current state
n Tape head is pointing to X
i
n X
1
X
2
…X
i-1
X
i
X
i+1
…X
n
are the current tape symbols
n d(q,X
i
) = (p,Y,R)  is same as:
X
1
…X
i-1
qX
i
…X
n
|---- X
1
…X
i-1
YpX
i+1
…X
n
n d(q,X
i
) = (p,Y,L)   is same as:
X
1
…X
i-1
qX
i
…X
n
|---- X
1
…pX
i-1
YX
i+1
…X
n