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.
Letbe 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.
Definition 4.2.
The five tupleis 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 machineis the four tuple
(= state of the regiser + tape content together with the position of the read-write head)
Remark 4.4.
A Turing machinehas a configuration in the form
if
or
.
Definition 4.5.
We say that the Turing machinefrom
in one step - or directly - (notation
), if
and exactly one of the following holds: 1)
, where
,
and
.d --- overwrite operation 2)
, where
and
. --- right movement operation 3)
, where
,
and
. --- left movement operation
Remark 4.6.
1. Sinceis 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
.
Definition 4.7.
A computation of a Turing machineis 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 machinemay 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
.)