17. Suppose that in Example 9.9 we had decided to represent x and y in binary.
Write a Turing machine program for doing the indicated computation in this
representation.
18. Sketch how Example 9.9 could be solved if x and y were represented in
decimal.
19. You may have noticed that all the examples in this section had only one final
state. Is it generally true that for any Turing machine, there exists another
one with only one final state that accepts the same language?
20. Definition 9.2 excludes the empty string from any language accepted by a
Turing machine. Modify the definition so that languages that contain λ may
be accepted.
9.2 Combining Turing Machines for Complicated
Tasks
We have shown explicitly how some important operations found in all computers
can be done on a Turing machine. Since, in digital computers, such primitive
operations are the building blocks for more complex instructions, let us see
howthese basic operations can also be put together on a Turing machine. To
demonstrate howTuring machines can be combined, we follow a practice
common in programming. We start with a high-level description, then refine it
successively until the program is in the actual language with which we are
working. We can describe Turing machines several ways at a high level; block
diagrams or pseudocode are the two approaches we will use most frequently in
subsequent discussions. In a block diagram, we encapsule computations in boxes
whose function is described, but whose interior details are not shown. By using
such boxes, we implicitly claim that they can actually be constructed. As a first
example, we combine the machines in Examples 9.9 and 9.11.
Example 9.12
Design a Turing machine that computes the function
f (x,y) = x + y if x ≥ y,
= 0 if x < y.
Write a Turing machine program for doing the indicated computation in this
representation.
18. Sketch how Example 9.9 could be solved if x and y were represented in
decimal.
19. You may have noticed that all the examples in this section had only one final
state. Is it generally true that for any Turing machine, there exists another
one with only one final state that accepts the same language?
20. Definition 9.2 excludes the empty string from any language accepted by a
Turing machine. Modify the definition so that languages that contain λ may
be accepted.
9.2 Combining Turing Machines for Complicated
Tasks
We have shown explicitly how some important operations found in all computers
can be done on a Turing machine. Since, in digital computers, such primitive
operations are the building blocks for more complex instructions, let us see
howthese basic operations can also be put together on a Turing machine. To
demonstrate howTuring machines can be combined, we follow a practice
common in programming. We start with a high-level description, then refine it
successively until the program is in the actual language with which we are
working. We can describe Turing machines several ways at a high level; block
diagrams or pseudocode are the two approaches we will use most frequently in
subsequent discussions. In a block diagram, we encapsule computations in boxes
whose function is described, but whose interior details are not shown. By using
such boxes, we implicitly claim that they can actually be constructed. As a first
example, we combine the machines in Examples 9.9 and 9.11.
Example 9.12
Design a Turing machine that computes the function
f (x,y) = x + y if x ≥ y,
= 0 if x < y.