Chapter 4. Turing machines

Everyone, who has some relation with informatics has an idea about the concept of algorithms. In the most case we can decide whether the thing under observation is an algorithm or not. At leas in the everyday case. Many of the people think on a computer program in connection with an algorithm, not without any reason. It is not clear, however, if a medical treatment or the walking are algorithms..

If we try to make the concept more exact, we reach some limitations. We have the following obvious expectations:

The algorithm should solve a well defined task or group of tasks.

The algorithm should stand of separable steps and the number of (different) steps are finite. We want the solution in limited time.

Every step of the algorithm should be well defined.

The algorithm need some input data for determining the particular task of the group of tasks. The amount of data should be finite, in any sense.

The algorithm should reply to the input. The answer should be finite and reasonable.

Clearly, if one wants to determine the concept of algorithm in a general manner, then some points will be not properly defined. The most critical part is the concept of "step". What does it mean "well defined"? If we give a precise definition, we would reduce our possibilities.

The precise determination of the concept of algorithms are was a subject of many mathematician in the first half of the last century. As a result, many different approach of the subject have arised, e.g. functions, recursive functions, Markov algorithm and Turing machine. Since these are well defined models, we have the feeling that they cannot be completely suitable for the substitution of the concept of the algorithm.

One can prove that the above models are equivalent, which means that every task which can be solved in one of the models, can be solved in all the others.

For the replacement of the concept of algorithm there are still no more general model than the listed ones. In the present lecture notes we will focus on the model of the Turing machine, since this is one of the most clear, easy to understand and expressive enough. Even if it is not so suitable for modeling the modern computer architectures.

With the help of Turing machines one can easily express the concept of computability, i.e. the algorithmic solvability and a precise measure can be introduced for describing the complexity of algorithms and problems.

If one wants to define with mathematical tools the concept of algorithms, the class of possible tasks should be reduced. One should exclude the mechanical operations on physical objects. This does not mean that, physical problems cannot be solved by some algorithmic way, but one have to model it first with some mathematical representation and then the result can be applied to the original problem through some interface.

We assume that the task and its parameters and input data can be represented in a finite way. Accordingly, we will give the input of an algorithm as a finite word over a finite alphabet and we expect the answer in the same way. Thus an algorithm can be regarded as a transformation, which maps words to words. Some of the algorithms have no reply on some input. These represents, so called, partial functions. One can find algorithms, which have only finitely many different answer on their infinitely many different inputs. These are the typical acceptor or decision machines.

Definition 4.1.

Let  be an alphabet,  be a language,  be a word 
and   be a transformation.
We will call algorithmic task (or simple task)
the following:
1. Determine if the relation   holds!
2. Determine the value of  !

The first kind of tasks are called decision problems,
while the second are called transformation problems.

Later we will see that the above easy looking decision problem in general is not easy at all. We will prove that there are problems such that one cannot even decide whether they are solvable or not.

Figure 4.1. The model of Turing machine

The model of Turing machine

4.1. The definition of the Turing machine

Definition 4.2.

The five tuple  is called Turing machine, if 
: is a finite nonempty set; set of states
: is a finite set with at least  elements and ; tape alphabet
; initial state
, nonempty set; final states
; transition function

The above formal definition needs a proper translation. One may think of the following "physical" model.

The Turing machine has three main parts:

1. a tape, infinite in both direction, divided into equal sized cells, containing symbols from the alphabet ;

the tape may contain only finitely many characters different from and they should be consecutive;

2. a register, containing values from , which determines the actual behaviour of the Turing machine;

3. a read-write head, pointing always to a particular cell, this connects a tape and the register.

One step of the Turing machine stands of reading the cell under the read-write head and depending on its value, executes some operation, determined by :

- writes back a symbol to the cell under the read-write head and changes it state or

- moves the read-write head to the neighbor cells and changes it state.

Usually the alternative definitions of the Turing machine sets the movement and write in the same step, but separating them makes some definitions much simpler.

The above semantics needs, however, a mathematically well defined "operation".

Definition 4.3.

A configuration of the Turing machine  is the 
four tuple  
(= state of the regiser + tape content together
with the position of the read-write head)

Remark 4.4.

A Turing machine  has a configuration in the form
  if  or .

Definition 4.5.

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

Remark 4.6.

1. Since  is uniquely defined for all  and , 
thus for all proper configuration either there exists a 
uniquely given direct accessible configuration  or
there are no any at all. 
2. By the definition of the configuration and the remark
after the definition if  and , 
then the Turing machine can execute a further step, 
if  or .
3. By the properties of the symbol , if  
and , then in the transition  the 
configuration .
Similarly, if  and , then in
the transition  the configuration 

Definition 4.7.

A computation of a Turing machine  is a sequence 
 of configurations  such that

1. , where ;
2. , if there exists a directly reachable 
configuration from  (and because of uniqueness, 
it is );
3. , if there are no directly reachable 
configuration from .

The word  is called the input of .

If  is such that , then 
we say that the computation is finite and the
Turing machine terminates in the final state .
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.8.

A Turing machine  may have infinite computation
on an input word  in two ways:
1.  there exist a directly reachable configuration ;
2.  such that from  there are no directly reachable
configuration and the state corresponding to  is not
a final state. (The Turing machine is "frozen" in the 
configuration .)