Evolutionary Synthesis of Rules for Programming the Turing Machine

Lukáš Kouřil, Ivan Zelinka

Abstract

This article deals with using artificial intelligence which is represented by Self-Organizing 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 program-generating  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 infinitely-sized memory is represented by infinitely-long data tape which modifications of the Turing machines work with. The data tape contains symbols of pre-defined 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 7-tuplet 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:

• Unary addition
• Divisibility
• Primality

Concrete parameters and settings of the Turing machine can be demonstrated on above-mentioned 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. Evolutionary-estimated generation of program for the Turing machine

 

Above-mentioned 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:

• There are set of paramters of the Turing machine (, , , , , )
• These parameters can be set in accordance with deliberation, previous observation or randomness.
• It is necessary to encode the problem which can be solved to the form of the data tape
• It is necessary to encode the result of the problem  which can be solved to the form of the data tape
• There must be set the initial position of the Turing machine’s head
• Artificial intelligence itself can compile the rules for the Turing machine control

 

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 above-mentioned instruction there can be found out some difficulties and problems:

• Whole process of the rules synthesis entirely depends on setting parameters of the Turing machine as are initial state, final state and number of inner states especially. If there is set e.g. insufficient amount of inner states, it may happen that the rules wan’t be designed properly or it will be imposible to design the rules.
• As shown formerly, there is necessary to regard solving problems not like manipulation with data tape symbols but understand their fundamentals. This can be a huge problem for proper designing of the rules by artificial intelligence.

 4.1 Employing the Self-Organizing Migrating Algorithm

As the suitable evolutionary algorithm, Self-Organizing 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:

• Cost function
  • This function establish a way how to calculate fitness of each individual.

• 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 Self-Organizing 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 3-tuplets of possible rules

 

The vector is compounded of 3-tuplets. 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”}

3-tuplet {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 3-tuplets. These 3-tuplets 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:

• An individual is rewritten to the form of the rules.
• The Turing machine is initialized by new rules and it is started.
• The output of the Turing machine is compared with requested output data tape.
• The rules are evaluated on the basis of the comparing (step 3)
• The evaluation of the rules represents new value of cost function.  In accordance with value of cost function are evaluated individuals.

 

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 time-consuming by whole process.

	Hit rate1 [%]	Steps2	Rules3
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

• Percentage rate of successfully designed rules
• Minimal number of steps of the Turing machine which lead to successfull solving of given problem
• Minimal number of rules, when the Turing machine operates as it is intended

 

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:

• The rules which are compiled by evolutionary algorithm unfortunately represent the program which solves problem with wholly concrete conditions. In our case it means, the evolution compiles the rules which solve concrete unary addition, i.e. 3 + 5, eventually other problem with concrete conditions.
• In the extreme case of divisibility problem, the Turing machine with new rules just rewrite „#” symbol to the “X” symbol without any calculations whether the number encoded to the data tape is prime-number or not. The artificial intelligence consider the problem just as the problem of symbol replacement in that way to input and output data tapes were same.
• In several cases of repeating evolutionary process for solving the unary addition problem, the evolution compiled universal rules. The Turing machine with those universal rules solves unary addition with diverse conditions too, not limited by 3 + 5 what is encoded in the data tape. The universality of the rules was verified by randomly generated input data tapes for the Turing machine. Overall 100 randomly generated data tapes were successfully proceeded by the Turing machine in order to verifying universality of the synthesized rules.
• Obtaining universal rules was not succeeded in the case of other mentioned problems.

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 Self-Organizing 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

• Hopcroft, John E., Motwani, Rajeev and Ullman, Jeffrey DIntroduction to Automata Theory, Languages, and Computation. 2nd. s.l. : Pearson Education, 2000. ISBN 0-201-44124-1.
• Lampinen, J. and Zelinka, I. New Ideas of Optimization - Mechanical Engineering Design Optimization by Differential Evolution. 1st. London : McGraw-Hill, 1999. ISBN 007-709506-5.
• Zelinka, Ivan. SOMA - Self Organizing Migrating Algorithm. [book auth.] B. V. Babu and G. Onwubolu. New Optimization Techniques in Engineering. s.l. : Springer-Verlag, 2004.
• Zelinka, Ivan. Umělá inteligence v problémech globální optimalizace. Praha :  BEN – technická literatura, 2002. ISBN 80-7300-069-5
• Zelinka, Ivan. SOMA, DE, Softcomputing. [Online] 4 12, 2010. http://www.fai.utb.cz/people/zelinka/soma/.
• Peterka, Jiří. Turing machine. Archiv článků a přednášek Jiřího Peterky. [Online] 3 17, 2010. http://www.earchiv.cz/a94/a432c120.php3.
• Turing machine. Wikipedia. [Online] 3 17, 2010. http://en.wikipedia.org/wiki/Turing_machine.
• Turing Machines implemented in JavaScript. The Alan Turing Internet Scrapbook. [Online] 2 10, 2010. http://www.turing.org.uk/turing/scrapbook/tmjava.html.