Genetic Algorithms and Turing Machine
Reflections on the use of a genetic algorithm for the Turing Machine.
There is some information obtained from the external environment, presented in a 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 execution of the modified program with the standard solution.
Take for example the simplest algorithm for MT. Increment binary number by one. It looks like this:
But we need to get it using a genetic algorithm.
')
For the genetic algorithm, the construction of the Turing Machine, we will need. Come up with a genome from a finite set of variations of chromosomes. Which will consist of a certain alphabet of commands for the Turing machine.
Divide the genome into compartments, the Chromosomes, each of them will represent the position of the Turing machine program, and divide the chromosome into 3 separate parts (so to speak, additional chromosomes) commensurate with the alphabet of the machine and in each part encode the action necessary to perform the machine.
Three actions will be encoded in binary:
And from this we have a command, in binary code, 5 bits in size.
Of the above, the genome will consist of three chromosomes, and those of 5x3 = 15 characters.
The individual will consist of 15x3 = 45 characters.
To implement the generation of the algorithm we need.
Genetic material.
C generated by the program generating random strings of binary code.
Breeding program.
Which will cross, past the selection of genotypes.
So to say "the Turing machine is the opposite."
In which the initial “Infinite” ribbon will be stored and the required, after passing from the genome generated by the genetic algorithm, its version.
Examples of tapes:
Starting tape - The end result.
0001-0010
0100-0101
1011-1,100
The requirement for a "Turing machine is the opposite."
The initial population is generated from binary code words. in five characters, 9 words long for each individual.
Individuals whose percentage of coincidence of the tape of the result with the reference tape is greater are passed to the selection of species.
Also with the same result. The individual whose length of gene is shorter than the other wins.
Selection of species occurs by exchanging the words of the genome of two subspecies that have approached the largest percentage of the result and the standard.
An integral part of evolution. In this case, there is a mutation of individual words of the representative of the species. 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 entrainment of the alphabet, or chromosomes, it is required to specify the rules for reading, rules for MT, 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.
Theoretically, the algorithms obtained by this type 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.
There is some information obtained from the external environment, presented in a 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 execution of the modified program with the standard solution.
Take for example the simplest algorithm for MT. Increment 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 a genetic algorithm.
')
1. Genetic engineering
For the genetic algorithm, the construction of the Turing Machine, we will need. Come up with a genome from a finite set of variations of chromosomes. Which will consist of a certain alphabet of commands for the Turing machine.
- if the character is "zero"
- if the symbol is "one"
- go to code part no.
- if there is no character
- move the carriage to the left
- move the carriage to the right
- wipe character
- write character 0
- write character 1
- stop program
Divide the genome into compartments, the Chromosomes, each of them will represent the position of the Turing machine program, and divide the chromosome into 3 separate parts (so to speak, additional chromosomes) commensurate with the alphabet of the machine and in each part encode the action necessary to perform the machine.
Three actions will be encoded in binary:
- The 1st and 2nd characters encode the character to be put into a readable code.
In this example.
The character is missing 00 ***
Null 01 ***
Unit 10 *** - The 3rd and 4th signs encode the chromosome number to which you want to go. Stop the program
q1 ** 00 *
q2 ** 01 *
q3 ** 10 *
STOP ** 11 * - The 5th digit encodes which way to move the reading head over the readable code.
R **** 0
L **** 1
And from this we have a command, in binary code, 5 bits in size.
Of 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 "Petri dishes"
To implement the generation of the algorithm we need.
Genetic material.
C generated by the program generating random strings of binary code.
Breeding program.
Which will cross, past the selection of genotypes.
So to say "the Turing machine is the opposite."
In which the initial “Infinite” ribbon will be stored and the required, after passing from the genome generated by the genetic algorithm, its version.
Examples of tapes:
Starting tape - The end result.
0001-0010
0100-0101
1011-1,100
The requirement for a "Turing machine is the opposite."
- To be able to read and process genetic material.
- Compare the result obtained on the tape, with its benchmark result, as a percentage of coincidence.
- To be able to identify the genome is not having the final result.
- Destroy the genome is not tested.
3. Generation of the initial population
The initial population is generated from binary code words. in five characters, 9 words long for each individual.
4. Population selection
Individuals whose percentage of coincidence of the tape of the result with the reference tape is greater are passed to the selection of species.
Also with the same result. The individual whose length of gene is shorter than the other wins.
5. crossing
Selection of species occurs by exchanging the words of the genome of two subspecies that have approached the largest percentage of the result and the standard.
6. mutation
An integral part of evolution. In this case, there is a mutation of individual words of the representative of the species. 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 entrainment of the alphabet, or chromosomes, it is required to specify the rules for reading, rules for MT, 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. the result
Theoretically, the algorithms obtained by this type 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.
Source: https://habr.com/ru/post/322370/
All Articles