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:**

moves the read-write head position to the right

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"

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:

.