Courses

# PPT: Turing Machines Notes | EduRev

## Computer Science Engineering (CSE) : PPT: Turing Machines Notes | EduRev

``` 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,
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,
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
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,
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
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
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,
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
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
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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## Theory of Computation

18 videos|44 docs|39 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;