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 .

Figure 4.36. The composition of The composition of and and The composition of and

The composition of and

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 .

Figure 4.37. Conditional composition of Conditional composition of , and, Conditional composition of , and and Conditional composition of , and

Conditional composition of , and

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

.

Figure 4.38. Iteration of Iteration of

Iteration of

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:

Composite Turing machines

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"

4. : moves the read-write head one to the left

5. : moves the read-write head one to the right

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:

.