Genetic Algorithms and a Turing Machine

Reflections on the application of the genetic algorithm for a Turing machine.

There is some information received from the external environment, presented in binary code, and there is a Turing Machine. And what if, take and apply the genetic algorithm to compile the Turing Machine program .
Which, in turn, will convert certain data, and compare the results of the modified program with the standard solution.

Take for example the simplest MT algorithm. Increasing a binary number by one. It looks like this:

1q1-> 1q1R
0q1-> 0q1R
Bq1-> Bq2L
1q2-> 0q2L
0q2-> 1q3L
Bq2-> 1STOP
0q3-> 0q3L
1q3-> 1q3L
Bq3-> BSTOPR

But we need to get it using the genetic algorithm.

1. Genetic engineering

For the genetic algorithm, the construction of the Turing Machine program, we need. Come up with a genome from a finite set of chromosome variations. Which will consist of a specific alphabet of commands for the Turing machine.

• if the symbol is "zero"
• if the symbol is "one"
• go to part of code no.
• if the character is missing
• move the carriage to the left
• move the carriage to the right
• overwrite symbol
• write character 0
• write character 1
• stop program

We divide the genome into compartments, Chromosomes, each of them will represent the position of the Turing machine program, and divide the chromosome into 3 separate parts (so to say additional chromosomes) in proportion to the alphabet of the machine and in each part we encode the action necessary to be performed by the machine.

Three actions will be encoded in binary:

• The 1st and 2nd character encode the character to be put in a readable code.
  In this example.
  No character 00 ***
  Zero 01 ***
  Unit 10 ***
  
  
• The 3rd and 4th character encodes the number of the chromosome to which you want to go. Program stop
  q1 ** 00 *
  q2 ** 01 *
  q3 ** 10 *
  STOP ** 11 *
  
  
• The 5th character encodes in which direction to move the read head, above the read code.
  R **** 0
  L **** 1

And from this we have a command, in binary code, 5 bits in size.

From the above, the genome will consist of three chromosomes, and those of 5x3 = 15 characters.
The individual will consist of 15x3 = 45 characters.

2. Preparation of the "Petri dish"

To implement the generation of the algorithm we need.

Genetic material.
With a generated binary line random code generation program.

Selection program.
Which will cross, past the selection of genotypes.

So to say, “Turing Machine is the other way around.”
In which the initial “Infinite” tape will be stored and the required version after passing through the genome generated by the genetic algorithm.

Examples of tapes:

Initial tape - The end result.
0001-0010
0100-0101
1011-1100

The requirement for a "Turing machine is the other way around."

1. Be able to read and process genetic material.
2. Compare the result obtained on the tape with your standard of result, in percentage of coincidence.
3. To be able to identify a genome that does not have an end result.
4. Destroy a genome that has not passed verification.

3. Generation of the initial population

The initial population is generated from binary code words. five characters, 9 words long for each individual.

4. Population selection

Individuals in which the percentage of coincidence of the result ribbon with the reference tape is greater, go to the selection of species.

Also with the same result. The individual whose gene length is shorter than the other wins.

5. crossbreeding

selection of species occurs by the exchange of words of the genome of two subspecies that fit the highest percentage of coincidence of result and standard.

6. mutation

An integral part of evolution. In this case, the mutation of individual words of the representative of the species occurs. Mutation also implies the addition of additional chromosomes, which is important for solving more complex problems. Adding additional words to chromosomes with an extension of the MT alphabet.

In the case of the entrainment of the alphabet, or chromosomes, the instructions for MT and reading rules must be indicated at the beginning of the genome. Since the change in the number of chromosomes and the number of letters in the alphabet will affect the number of bits / gene in the genome.

7. total

Theoretically, the algorithms obtained in this form will be the most compact and efficient.
And most importantly, understandable to man.

Thanks for attention.

This is my first article on Habrahab. I plan to move from theory to practice, with further writing of the article.