4.2 Examples of Turing Machines
B/B, L B/B, R B/B,L
l/B, LFigure 4.8: Procedure E.
Solzsti~n. We create two procedures. The first one, E, erases a block of 1’s.
That is, for any it: E (1, B} and y f {l}, it has the effect of
The transition diagram of procedure E is shown in Figure 4.8.
The second procedure, P, erases the second rightmost block of 1’s. That
is, for any x E { 1, B} and y, x E {l}, it works as follows:
(s, xByBzE3) t-* (h, xBzE3).
Procedure P can be implemented exactly as shown in Figure 4.6.
Now, we can combine procedures E and P together to form a new machine
A& that computes 7~ k. The machine iV looks like this:
In the above, by X + Y we mean that the state h of procedure X is identified
with state s of procedure Y (and is a new state of &! which is neither the
final state nor the initial state). So, the above picture means that machine
&! first erases the rightmost k - i blocks of l’s, skips a block of l’s, and then
erases i - 1 more blocks of 1 ‘s.
We express the machine AL! as EkBiPiml. cl
The following example further demonstrates the technique of combining
Turing machine procedures to create more complicated Turing machines.
First, we extend the notion of Turing-computability to functions with more
than one output. A partial function f : (E)m + (IZ)n is Turing-computable
if there is a DTM hl such that for every input (xl, x2,... , xm) E (C*)m, if
f(x1, x2, ’ l l I xm) is defined and is equal to (yr, ~2,... , yn>, we have
(s, Bx1Bx2B l l -Be&l) 1; (h, BylBy2B l l l By,B), -
and if f (x1, x2,... , x,J is undefined, hl does not halt when it starts from the
initial configuration (s, BxlBx2B l. l Bx,B).
Example 4.9 Show that, for any 1 < - i < - Ic + 1, the function
inserti k (xl, x2, l l. , xk, y) = (xl,... , x&l, y, xi,... , xk)