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

Download, print and study this document offline
Please wait while the PDF view is loading
 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
Read More
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on PPT: Turing Machines - Theory of Computation - Computer Science Engineering (CSE)

1. What is a Turing machine in computer science engineering?
Ans. A Turing machine is a theoretical computing device that consists of an infinite tape divided into cells, a read/write head that can move left or right on the tape, and a control unit that determines the machine's behavior based on its current state and the symbol being read.
2. How does a Turing machine work?
Ans. A Turing machine works by following a set of rules defined in its transition function. It starts in an initial state, reads a symbol from the tape using its read/write head, and based on the current state and the symbol, it updates its state, writes a new symbol on the tape, and moves its head left or right. This process continues until the Turing machine reaches a halting state.
3. What is the significance of Turing machines in computer science engineering?
Ans. Turing machines are significant in computer science engineering as they form the foundation of theoretical computer science. They help in understanding the limitations and possibilities of computation, and they provide a theoretical framework for studying the complexity of algorithms and the notion of computability.
4. Can a Turing machine solve any problem?
Ans. Yes, a Turing machine can solve any problem that is algorithmically solvable. However, it is important to note that solving a problem using a Turing machine does not necessarily mean that it can be solved efficiently or practically in real-world scenarios.
5. Are Turing machines still relevant in modern computer science engineering?
Ans. Yes, Turing machines are still relevant in modern computer science engineering. Although they are a theoretical construct, they provide a fundamental understanding of computation and serve as a basis for designing and analyzing algorithms and programming languages. Additionally, they are used in theoretical research and form the basis for various computational models.
18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

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

,

Exam

,

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

,

MCQs

,

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

,

Semester Notes

,

ppt

,

study material

,

practice quizzes

,

Objective type Questions

,

Free

,

Extra Questions

,

pdf

,

Viva Questions

,

past year papers

,

Previous Year Questions with Solutions

,

video lectures

,

mock tests for examination

,

Important questions

,

Summary

,

shortcuts and tricks

,

Sample Paper

;