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