Lukáš Kouřil, Ivan Zelinka
Abstract
This article deals with using artificial intelligence which is represented by SelfOrganizing Migrating Algorithm for programming the Turing machine. During research which is described below we tried to simplify programming process of the Turing machine. The programming process consists of designing reponses of the Turing machine’s transfer function in the form of the rules which describe operating of the machine.This process was successfully covered up by evolution which produce the rules for solving concrete tasks by the Turing machine. Thus we prove possibility to employ artificial intelligence at simplifying complicated programming the Turing machine.
1. Introduction and motivation
Turing machines [1], [6] – [8] represent the tools for theoretical solving problems, which are unsolvable by current techniques and common devices hence there exist limitations of them. Above all, there are hardware limitations of computers which executes complex computations. The Turing machine can deal with those limitations of computers and similar devices at the cost of highly complicated programming (composition of rules for controlling the Turing machine) however. Our approach to programming the Turing machine makes possible to simplify programming itself. The simplification consists in application of artificial intelligence [4] in such a way that programgenerating process uses evolutionary computational techniques of artificial intelligence for composition of rules for the Turing machine according to intended actifity of the machine. It can be said the machine programs the machine.
2. Fundamentals of the Turing machines
The Turing machine is ranked among theoretical automata which use sequential approach to operations and which are capable to solve problems whose common processing exceeds limitations of existing machines (computers, computational techniques, devices etc.) As the first one of those limitations, there is infinite storage size of memory [6]. This infinitelysized memory is represented by infinitelylong data tape which modifications of the Turing machines work with. The data tape contains symbols of predefined signary. The Turing machine consists of the record medium – the data tape which serves for reading and writing, and the read/write head. The Turing machine frequently pursues quite simple activity – reads symbol from the tape, writes new symbol on the tape, moves the head and pass on to new state. What new symbol is written on the tape and what is direction of the head movement depend on the inner state of the machine and symbol, which is currently read. The program for activity control of the Turing machine is presented by table which contains assignments of new inner state of the Turing machine, symbol for writing and information on direction of the head movement. These are assigned to the current state of the machine and symbol which was read.
The Turing machine can be formally described by 7tuplet which contains following parameters:
, where
– set of inner states of the machine
–set of input symbols
– tape symbols
– transfer function, where , whereas q is current inner state of the machine, X is symbol loaded from the tape, p is next state of the machine, Y is symbol, which has to be written on the tape, D is direction of the head movement – left, right, stagnation.
– initial state
– blank symbol for filling empty spaces on the tape
– set of final or accepting states
Labelling of parameters is based on definition of the Turing machine [1].
3. Programming the Turing machine
Programming the Turing machine consists of designing the table, which maps responses of the Turing machine to the input of the transfer function. The table represents assignment and establishes what way the machine is operating. The contents of the table are indicated as the rules of the Turing machine. The aim of the programming the Turing machine is to design the table in the way that the machine transform the input tape to the form that we request.
Activity of the Turing machine is frequently demostrated at elementary problems [8] which are:
Concrete parameters and settings of the Turing machine can be demonstrated on abovementioned elementary problems. Following examples are used as study cases of evolutionary synthesis of the rules.
3.1 Unary addition
Unary addition represents very simple math problem of addition which is realized in unary number system.
If there is taken into account math example
3 + 5
In the unary number system it looks like
111 + 11111
Result is 11111111
The data tape encodes the math example to the the form of array of the symbols.
… 
# 
# 
# 
1 
1 
1 
# 
1 
1 
1 
1 
1 
# 
# 
# 
… 
Figure 1  Example of the data tape for unary addition 3 + 5 problem
It is requested a response from the Turing machine. The output of the Turing machine is modification of the data tape which represents the result of the math example which was encoded to the unmodified form of the data tape.
… 
# 
# 
# 
1 
1 
1 
1 
1 
1 
1 
1 
# 
# 
# 
# 
... 
Figure 2  The data tape modificated by response of the Turing machine (unary addition 3 + 5 problem)
Parameters of the Turing machine can appear as follows:
The number of inner states which can be set in accordance with deliberation. But there is a risk of the Turing machine malfunction if there is set too little inner states!
Because the only active symbol of unary addition problem is number 1, this parameter contains only one symbol too.
= {“#”, ”1”}
The data tape contains active symbols and blank symbols.
As the initial state is set qA state in this case. The initial state can be set in accordance with deliberation.
Blank symbol which represents blank places in the data tape. Any symbol can be stated as blank.
The final state. When this state is passed, the Turing machine ends operating. We can chose any state as final.
Transfer function is described by following table:
Argument of transfer function  The Turing machine response  
Current state 
Loaded symbol 
Next state 
Symbol for writing 
Head movement 
qA 

qD 

1 
qA 

qC 

1 
qB 

qC 

1 
qB 

qD 

1 
qC 

qF 

0 
qC 

qB 

1 
qD 

qC 

1 
qD 

qD 

1 
qE 

qE 

1 
qE 

qF 

0 
Table 1  Rules of the Turing machine activities
Rem.: Head movement 1 means the direction of the move to the right, 1 to the left, 0 without movement.
The last parameter which is required to run the Turing machines is the initial position of the head. In the case of this example problem the initial position is set at first blank symbol before active symbol.
On the basis of the above, it can be shown first seven steps of the Turing machine activity:
1.
… 
# 
# 
# 
1 
1 
1 
# 
1 
1 
1 
1 
1 
# 
# 
# 
... 
2.
... 
# 
# 
# 
1 
1 
1 
# 
1 
1 
1 
1 
1 
# 
# 
# 
... 
3.
... 
# 
# 
# 
1 
1 
1 
# 
1 
1 
1 
1 
1 
# 
# 
# 
... 
4.
... 
# 
# 
# 
1 
1 
1 
# 
1 
1 
1 
1 
1 
# 
# 
# 
... 
5.
... 
# 
# 
# 
1 
1 
1 
# 
1 
1 
1 
1 
1 
# 
# 
# 
... 
6.
... 
# 
# 
# 
1 
1 
1 
1 
1 
1 
1 
1 
1 
# 
# 
# 
... 
7.
... 
# 
# 
# 
1 
1 
1 
1 
# 
1 
1 
1 
1 
# 
# 
# 
... 
3.2 Divisibility
The divisibility problem can solve math examples of exact division of two numbers. There is considered math example of exact divisibility 8 / 4. If the problem is transcribed to the form of data tape, the modified notation of the problem follows:
... 
# 
# 
# 
1 
1 
1 
1 
# 
1 
1 
1 
1 
1 
1 
1 
1 
# 
# 
# 
... 
Figure 3 – Example of the data tape for 8 / 4 exact divisibilty problem
Requested modifiication of the data type looks like this:
... 
# 
# 
# 
1 
1 
1 
1 
X 
1 
1 
1 
1 
1 
1 
1 
1 
# 
# 
# 
... 
Figure 4  Requested output form of the data type
If the arguments of math example are exactly divisible, blank symbol between arguments in unary number system is rewritten to the „X“ symbol.
This problem is much more complicated than previous. The Turing machine needs to understand symbols on the data tape as arguments of math example and to check, whether arguments which are encoded on the data tape are realy exactly divisible. For that reason, there must be many more inner states of the Turing machine and the table which contains the rules for the Turing machine must be much extensive.
3.3 Primality
The aim of solving this problem is to detect whether the number which is encoded on the data tape is prime number or not. Primality detection is realized by similar principles which are used in the divisibility problem.
The input data type can appear as follows:
... 
# 
# 
# 
1 
1 
1 
1 
1 
1 
1 
# 
# 
# 
... 
Figure 5  Example of the data type for primality detection of number 7
If number which is encoded in unary number system on the data type is prime number, the modified data type should look like:
... 
# 
# 
X 
1 
1 
1 
1 
1 
1 
1 
# 
# 
# 
... 
Figure 6  Response of the Turing machine (primality was detected)
Solving of this problem is highly complex and requires a multitude of inner states. Composition of the table which contains the rules for the Turing machine control represents extremely complicated task. These rules must provide information on algorithm of prime numbers classification for the Turing machine.
4. Evolutionaryestimated generation of program for the Turing machine
Abovementioned findings result that it is not simple to arrange the table which contains the rules assigning arguments of the transfer function to the response from the Turing machine thus a program for the Turing machine. Complications which occure in the development process of the program for the Turing machine represent the problem which can be tried to solve by recent computational methods [2] – [5]. These methods we use belong to methods which utilize components of artificial intelligence, especially evolutionary methods. It can be said we let machine to program another machine.
The idea of employing evolutionary methods for composition of the rules for the Turing machine consists of following statements:
At first sight, these statements represent generally universal instructions how to obtain the rules for solving whatever problem by the Turing machine. Nevertheless, If there is taken a think of abovementioned instruction there can be found out some difficulties and problems:
4.1 Employing the SelfOrganizing Migrating Algorithm
As the suitable evolutionary algorithm, SelfOrganizing Migration Algorithm (SOMA) [3] – [5] was chosen. SOMA is algorithm which is based on priciples of genetic algorithms and evolution. There is actually considered evolution as it is known in the nature. Algorithms which are ranked as evolutionary are instrumental to optimization. Optimization results from natural processes of selection which proceed among living organisms. This selection values each individual in dependence on its parameters and the individual with the best evaluation „survives“. It is the same as process in the nature, when the individual of actual generation which is most adapted to sorrounding environment really survive.
This algorithm is described in e.g. [3], [5].
SOMA is a stochastic optimization algorithm that is modeled on the social behaviour of cooperating individuals [3]. It was chosen because it has been proven that the algorithm has the ability to converge towards the global optimum [3]. SOMA works on a population of candidate solutions in loops called migration loops. The population is initialized randomly distributed over the search space at the beginning of the search. In each loop, the population is evaluated and the solution with the highest fitness becomes a leader . Apart from the leader, in one migration loop, all individuals will traverse the input space in the direction of the leader. Mutation, the random perturbation of individuals, is an important operation for evolutionary algorithms. It ensures the diversity amongst the individuals and it also provides the means to restore lost information in a population. In the case of SOMA, mutation is ensured by a parameter called PRT which achieves perturbation.
The novelty of this approach is that the PRT Vector is created before an individual starts its journey over the search space. The PRT Vector defines the final movement of an active individual in search space.
The randomly generated binary perturbation vector controls the allowed dimensions for an individual. If an element of the perturbation vector is set to zero, then the individual is not allowed to change its position in the corresponding dimension.
An individual will travel a certain distance (called the PathLength) towards the leader in n steps of defined length. If the PathLength is chosen to be greater than one, then the individual will overshoot the leader. This path is perturbed randomly.
The SOMA algorithms itself has following parameters:
Specimen
Specimen encodes parameters we need to optimize in the form of individual for evolution.
Population size
How many individuals is contained in one generation / migration.
Migrations
How many migration steps will proceed.
Step
The size of step which individuals can do on the migration way.
Path length
Path duration which individuals migrate.
PRT
Perturbation vector of the migration process.
Minimal diversity
This parametr brings some of diversity to the evolutionary process.
In short, at the beginning there is defined a specimen. The specimen represents the form of all individuals which are processed by evolutionary algorithm. The specimen contains parameters we want to optimize by evolution. In our case it means that specimen encode the rules for the Turing machine we want to obtain. Then the first generation, in SOMA it is called as migration, is generated. Parameters of individuals of the first migration are presetted randomly in dependence on specimen specification. Subsequently there proceeds an optimization of individual parameters. The optimization is described in fitness function of evolutionary algorithm. This function evaluates individuals too. Individuals which are preferably evaluated proceed to the next generation. Other individuals become extinct and new individuals are generated. The speciality of SOMA algorighm is an imitation of nature process when wildlife migrates to the new locations because of food. The optimization consists of migration of individuals and recalculating their parameters in dependence on direction of evolution.
There are several variations of SOMA algorithm which vary by way of migration. In this case we have chosen SOMA_All_To_One variation, where individuals migrate past the best one.
4.1.1 Specifying SOMA parameters
On the basis of parameters mentioned in 4.1 Employing the SelfOrganizing Migrating Algorithm, the evolutionary process optimizes the rules which were set randomly in the first migration. Two of most important parameters which essentialy influence the evolution are specimen and cost function. Because evolution algorithm as well as other computational methods uses numerical expressions, it is necessary to encode the rules of the Turing machine to the numerical form. Common form of the rules looks like below:










Figure 7 Sample set of the Rules
Other form is e.g. Table 1 – Rules of the Turing machine activities.
As can be seen above (Figure 7 – Sample set of the Rules and Table 1 – Rules of the Turing machine activities), the left side of the rules contains arguments of the transfer function. These arguments are combinations of inner states of the Turing machine and the data tape symbols which are loaded by the Turing machine. This finding is used for encoding the rules to the form of specimen. Then the second subject which is used for encoding the rules to the form of specimen is a vector containing all possible transfer function reponses in the manner of combinations of the Turing machine’s inner states, symbols for writing and directions of head movement.
Figure 8  Part of vector containing 3tuplets of possible rules
The vector is compounded of 3tuplets. The first number is an index of new inner state, the second number is an index of data tape symbol which should be written, the third number express direction of head movement.
E.g.:
If set of inner states and set of data tape symbols look like following:
= {“#”, ”1”}
3tuplet {1,2,1} can be decoded as (qA, “1”, left direction).
Then the specimen is a vector which contains indexes of items of all possible rules in the form of 3tuplets. These 3tuplets represents the right side of the rules – responses of the transfer function, which are mapped to the left side of the rules by following way.
Figure 8  Encoding of the rules
The next important part of the evolution is the cost function. The cost function proceeds following:
Other SOMA parameters which were used:
Parameter 
Value 
Population size 
60 – 100 
Migrations 
60 – 100 
Path length 
3 
Perturbation 
0.1 
Minimal diversity 
1 
Table 2  Parameters of SOMA
5. Results
The evolutionary process which optimizes the rules for each problem was repeated 10 times. This relative small number of repeating was chosen by reason of high timeconsuming by whole process.
Hit rate^{1} [%]  Steps^{2}  Rules^{3}  
Unary addition  70  19  10 
Divisibility  100  2  36 
Primality  100  16  72 
Table 3  Hit rates of successfully designed rules for solving example problems
The rules we obtain by SOMA were set to the Turing machine which had subsequently proven to successfully solve given problems. Nevertheless during verifying designed rules it was founded out that:
Typical history of evolution processes can be seen below.
Figure 9  History of the evolutionary process in the case of unary addition problem
Figure 10  History of the evolutionary process in the case of divisibility problem
Figure 11  History of the evolutionary process in the case of primality problem
6. Conclusion
We tried to employ evolutionary algorithm at designing of the rules for the Turing machine. As the suitable algorithm we have chosen SelfOrganizing Migrating Algorithm, especially SOMA_All_To_One modification. During research we tried to syntesize the rules for three elementary problems which were mentioned hereinbefore. The evolution provides very powerful instrument for solving these problems, because there are generated entirely uniq sets of rules at every start of the evolutionary process. We prove the evolution can be successfully employed at designing the rules for programming the Turing machine. Nevertheless, the rules designed by evolutionary process are suitable only for problems with specified concrete conditions as it was found out later.
As the next step of this research we will try to optimize the cost function of evolutionary algorithm in such way the evolution will solely produce compilations of universal rules for all elementary problems we use in our research.
Acknowledgement
This research is a part of the project „Evolutionary Synthesis of Biomolecular Structures“, no. IGA/42/FAI/10/D, which is supported by the Internal Grant Agency of Tomas Bata University and the Grant Agency of the Czech Republic, no. GACR 102/09/1680.
References
Aktuální číslo
Odborný vědecký časopis Trilobit  © 2009  2019 Fakulta aplikované informatiky UTB ve Zlíně  ISSN 18041795