Section 9.4 Turing Machines
779
• Turing machines can be used as set recognizers and
as function computers.
• The Church–Turing thesis equates a function
computable by an algorithm with a Turingcomputable function. Because this thesis expresses
a relationship between an intuitive idea and a
formally defined one, it can never be proved but
has nonetheless been widely accepted.
• A decision problem asks if an algorithm exists to
decide whether individual statements from a large
class of statements are true; if no algorithm exists,
the decision problem is unsolvable.
• The halting problem is unsolvable.
• P # NP, but it is unknown whether P ( NP.
exeRciSeS 9.4
For Exercises 3–26, be sure to include comments with any Turing machine definition.
1. Consider the Turing machine
(0, 0, 0, 0, L)
(0, 1, 0, 1, R)
(0, b, b, 0, L)
(1, 0, 0, 1, R)
(1, 1, 0, 1, R)
a. What is its behavior when started on the tape
b
...
0
1 0
1 1 b ...
b. What is its behavior when started on the tape
b
...
1
0 0
1 1 b ...
2. Consider the Turing machine
(0, 1, 1, 0, R)
(0, 0, 0, 1, R)
(1, 1, 1, 1, R)
(1, b, 1, 2, L)
(2, 1, 1, 2, L)
(2, 0, 0, 2, L)
(2, b, 1, 0, R)
a. What is its behavior when started on the tape
b
...
1
1 0
0 b ...
b. What is its behavior when started on the tape
b
...
1 0 1 b ...
3. Find a Turing machine that recognizes the set of all unary strings consisting of an even number of 1s (this
includes the empty string).