4.5. Composition of Turing machines

In many cases the Turing machine solution for a given task is not obvious. One may define, however, some general operation on Turing machines, with which more complex Turing machines can be constructed from simpler ones. Using these operations many of the proofs became easier. It extends the possibilities to apply our standard approach for programming, while the mathematical accuracy is preserved.

Definition (composition of Turing machines) 4.15.

```Let  and
be two Turing machines and assume that
.
The Turing machine  (or )
is defined by the following:
, where
,
,
,
and
.
Here

where
, for all  and ,
and
for all  and .```

Remark 4.16.

```The union of the functions  is defined
on the way given in Chapter 2 as the union
of relations. ```

Theorem 4.17.

```The Turing machine  defined above has
the property ,
i.e.  can be regarded as the consecutive
execution of  and . ```

Proof

Let be a word of arbitrary length .

The computation of on the input word is , while the computation of on the input word is .

If terminates on the input word , let and the let computation of on the input word be .

By definition, since , thus .

Again, by definition, if , then , i.e. while we have .

Hence, if does not terminate on , then does not terminate, neither.

If , where , then terminates. In this case , i.e. the content of its tape is .

By definition, continues computing according to , i.e. it goes to the configuration and then it moves the read-write head back to the beginning if the tape. When it reaches the first symbol, it transits to the configuration - here -, but this is equal to the configuration .

Since , if , thus for the next steps, i.e., if does not terminate on , then does not terminate, neither.

Otherwise .

Using acceptor Turing machines, the conditional execution can be defined, too.

Definition (conditional execution) 4.18.

```Let ,
and  be three Turing machines.
Assume that
,  ,  ,
and   .
We define the Turing machine
by the following:
, where
,
,
,
and
.
Here
,
where
for all  and ,
for all  and ,
for all  and
furthermore
, where .
```

Remark 4.19.

```Multiple conditional execution can be
defined by splitting  to more than 2 parts
and assigning to each part a new Turing machine.```

Theorem 4.20.

```Let  and  and denote the answer
of  by , if it terminates in a state from
on the input  and denote the answer by ,
if it terminates in a state from  on the
input .
The above defined Turing machine   has:
, if the answer of  on the input
word  is  or
, if the answer of  on the input
word  is .```

Proof

Let be a word of arbitrary length . The computation of on the input word is , while the computation of

on the input word is . If terminates on , let and the computation of on is , while the computation of on is .

By definition, since , thus .

Again by definition, if , then , i.e. while , we have .

Hence, if does not terminate on, then does not terminate, too.

If , where , then terminates. In this case , i.e. the content of the tape is .

By definition, continues computing according to .

a.) If , then first it goes to the configuration and then it moves the read-write head back to the beginning if the tape. When it reaches the first symbol, it transits to the configuration - here -, but this is equal to the configuration .

Since , if , thus for the next steps, i.e., if does not terminate on , then does not terminate, neither.

Otherwise

b.) If , then first it goes to the configuration and then it moves the read-write head back to the beginning if the tape. When it reaches the first symbol, it transits to the configuration - here - , but this is equal to the configuration .

Since , if , thus , for the next steps, i.e., if does not terminate on, then does not terminate, neither.

Otherwise .

If one would like to execute a Turing machine repeatedly in a given number of times, then a slight modification of the definition is required, since we assumed that the set of states of the Turing machines to compose are disjoint.

Definition (fixed iteration loop) 4.21.

```Let  be a Turing machine.
The Turing machine  is
defined such that the corresponding
components of  is replaced by a
proper one with a  sign.
With this notation let
.
In general:
Let  and
, if .```

Remark 4.22.

```By Theorem 4.17. .
Iteratively applying, we have
, where the
depth of embedding is .
(The notation of  is just the same
as it is usual at composition of
functions.)

The Turing machine denoted by
can be regarded as the consecutive
execution of  repeated  times. ```

There is one tool missing already from the usual programming possibilities, the conditional (infinite) loop.

Definition (iteration) 4.23.

```Let  and
,  .
The Turing machine
is defined by:
, where
,
,
,
and
.
Here

, where
for all  and ,
,  and
. ```

Remark 4.24.

```If , then  does not terminate
on any input (= infinite loop).```

Theorem 4.25.

```            ,
i.e.  can be regarded as the iterative
execution of .```

Proof

Let be a word of arbitrary length .

The computation of on the input word is , while the computation of on the input word is .

If terminates on the input word .

By definition, since , thus .

Again, by definition, if , then , i.e. while we have

By this, if does not terminate on, then does not terminate, neither.

If , where , then terminates. In this case , i.e. the content of its tape is .

By definition, if continues computing according to , if it terminates.

If , then it goes to the configuration and then it moves the read-write head back to the beginning if the tape. When it reaches the first symbol, it transits to the configuration - here -, but this is equal to the initial configuration of with the input word .

Then , i.e. it behaves as it would start on the input

.

Remark 4.26.

```One may eliminate the returning of the read-write
head to the beginning of the tape. Then the
execution of the next Turing machine continues
at the tape position where the previous one has
finished its computation. In most of the cases
this definition is more suitable, but then it
would not behave as the usual function composition.```

Using these composition rules, we may construct more complex Turing machines from simpler ones.

Some of the simpler Turing machines can be the following:

• observes cell on the tape, the answer is "yes" or "no"

• moves the read-write head to the first or last position of the tape

• writes a fixed symbol to the tape

• copies the content of cell to the next (left or right) cell

• ...

Composite Turing machines

• writes a symbol behind or before the input word

• deletes a symbol from the end or the beginning of the input word

• duplicates the input word

• mirrors the input word

• decide whether the length of the input word is even or odd

• compares the length of two input words

• exchanges representation between different number systems

• sums two words (= numbers)

Example

Let be the set of possible input words and let the following Turing machines be given:

1. : observes the symbol under the read-write head; if it is a ,then the answer is "yes" otherwise the answer is "no"

2. : observes the symbol under the read-write head; if it is a ,then the answer is "yes" otherwise the answer is "no"

3. : observes the symbol under the read-write head; if it is a ,then the answer is "yes" otherwise the answer is "no"

6. : writes a symbol on the tape

7. : writes a symbol on the tape

8. : writes a symbol on the tape

Applying composition operations, construct a Turing machine which duplicates the input word, i.e. it maps to !

First we create a Turing machine for moving the read-write head to the rightmost position:

.

The leftmost movement can be solved similarly:

The Turing machine which search for the first to the right is the following:

.

The Turing machine which search for the first to the left is the following:

.