4.6. Multi tape Turing machines, simulation

One can introduce the concept of multi tape Turing machine as the generalisation of the previous model. Here the state register of the Turing machine has connection with more than one tape and every tapes has its own independent read-write head.

Figure 4.39. Multi tape Turing machine

Multi tape Turing machine

Definition (multi tape Turing machine) 4.27.

Let  be an integer. The  tuple 
 is called a -tape
Turing machine, if ha 
 is a finite, nonempty set; set of states
 is a finite, nonempty set; ; tape alphabet
; initial state
, nonempty; final states
; transition function

Similarly to the simple (single tape) Turing machines, one may define the concept of configuration, step and computation.

Definition 4.28.

Let  be -tape Turing machine and
.
 is called the set of possible configurations
of , while its elements are called the possible 
configurations of .
Then  is the set of possible description
of one tape of .

Definition 4.29.

Let  be a -tape Turing machine
and let  be two configurations of it.
Assume that 


            
where , ,
,
 
            
and
, where .
We say that the Turing machine   
             
reach the configuration from 
             in 
one step - or directly - (notation ), 
if for all  exactly one of the 
following holds:
1) 
   
             and
   , where .
   --- overwrite operation
2) ,
    and
   .
   --- right movement operation
3) ,
    and
   .
   --- left movement operation

Remark 4.30.

The multitape Turnig machines execute 
operations independently - but determined 
together by its transition function - on 
its tapes.

Definition 4.31.

Let  be a -tape Turing machine. 
A computation of the Turing machine 
 on the input word  of length  
is a sequence  of 
configurations such that
1. , where  and
    , if ;
2. , if there exists a 
directly reachable configuration 
from  (and because of uniqueness, 
it is );
3. , if there are no 
directly reachable configuration 
from .

If  is such that , 
then we say that the computation is 
finite and the Turing machine terminates 
in the final state . 
If , then the word  
is called the output of .

Notation: .

If for a word  the Turing machine  
has an infinite computation, then it has 
no output. 
Notation:  . (Do not mix it up with 
the output .)

Remark 4.32.

It is assumed in the definition of the
multitape Turing machines, that the
input and output are on the first tape.
This is a general convention, but of 
course in particular cases the input or
output tapes can be elsewhere. 

Obviously, the multi tape Turing machine model is at least as strong as the original, single tape model, since every single tape Turing machine can be extended by arbitrary number of tapes, which are not used during computations. These single and multi tape Turing machines are identical from operational point of view.

To observe the strength of the different models, we need a precise definition to describe the relation of models.

Definition 4.33.

Let  and  be two Turing machines. 
We say that  simulates , if 
and  the equality  holds. 

Remark 4.34.

By Definition 4.34., arbitrary input of  
is a possible input of , too.
Furthermore,  means that if   
terminates on the input word  and it computes
the output word , then  terminates and
gives the output , too. If  does not terminate
on the input , then  not terminate, neither.
It is possible, that  can compute many more,
than , but it can reproduce the computation of .

Theorem 4.35.

Let  be  a -tape Turing machine.
Then  there exist a  
               -tape Turing 
machine, which simulates .

Proof

The complete proof would yield the elaboration of many technical details, thus only a rough proof is explained.

The proof is constructive, which means that define a suitable Turing machine here and prove that it is the right one.

The basic idea of simulation is that we execute the steps of the original Turing machine step by step.

For this purpose, the simulating Turing machine continuously stores the simulated one's actual configurations. In general, one may observe, that a Turing machine can store information in two ways: by the states and on the tapes. Since there are only finitely many states and the number of configurations are infinite, it is natural to store the necessary data on the tape. Since the simulating Turing machine has only a single tape, thus all information should be stored there. There are many possibilities to do so, but we will choose the one, which divides the tape into tracks and uses them to store the tapes and position of the read-write heads of the original Turing machine. In this case the symbols of the new Turing machine are -component vectors of the original symbols extended by a - component vector of 's for the positions of read-write heads.

The definition of then:

Let be the Turing machine which simulates , where

and

is the transition function, described below:

As it is explained at the beginning of the proof, we will store on the tape of all information of the original Turing machine. In the meantime the state of stores among others, the actual state of .

Initially, we will assign the configuration of for the configuration of by the following way:

The components of are

,

, where if and , or otherwise,

furthermore

, where (i.e. the length of is longer by one, than the longest word on the tapes of ),

for all , where (if , then let ) and

, if or otherwise (i.e. the read-write head is over the th position of tape ), for all and .

In a particular -tape case it looks like:

Figure 4.40. Simulation of a two-tape Turing machine

Simulation of a two-tape Turing machine

The Turing machine executes the following computational phases from an above given initial state:

Phase 1. Reading

Scan the tape and where it finds at a read-write position, the corresponding symbol is stored in the corresponding component of the state.

In the example above, until the fourth step, is unchanged. Afterward, it takes the value . After the fifth step it changes again to the value .

If it read the last nonempty cell on the tape, it steps to the next phase.

In the example, the state of does not change further in this phase, since there are no more read-write head stored on the tape.

Phase 2. The execution of the step .

In this phase it does only one thing: if , then it goes to the state , where

Actually, it computes and stores in its state the simulated Turing machine's transition (state change, tape write and movement).

Then it continues with phase tree.

Phase 3. Writing back.

By the new state it changes the content of the tape. Moving backward, it searches the positions of the read-write heads denoted by 's and observes in the state what operation should be executed. If some tape symbol have to be changed, then it replaces the proper with the corresponding . If the read-write head have to be moved, then it erases the value from the proper component of the given cell and writes it to the same component of the next cell (left or right, depending on the value of ).

These steps are more complicated, thus they cannot be realised by a single state. Thus the last component of should be changed accordingly. ( denotes the different steps in the phase),

If the first cell of the tape is reached, it continues with phase four, which is denoted by the value for the last component of the state.

Phase 4. Normalizing

This phase is the most complex. If extends or erases any of its tapes, then the tracks start to moves away on the tape of . This should be corrected to achieve the same form as the original initial configuration.

After normalisation, the computation may be continued in two ways.

If the state contains a final state as a component, then it transits to the state , if is not a final state, then it transits to the state . In this latter case the Turing machine arrives to a configuration suitable for phase 1. and continues its computation.

If starts from a configuration corresponding to the initial configuration of , then at the phase change 4.-1. exactly executes the steps of the computation of . It will terminate exactly when the original Turing machine would terminate, too. The content of its tape corresponds to the content of the tape of . I.e. really simulates . ✓

Problem

1. Write a Turing machine for computing the Ackermann function!