Есть некая информация получаемая из внешней среды, представленная в бинарном коде, и есть Машина Тьюринга. А что если, взять и применить генетический алгоритм для составления программы Машина Тьюринга.
Которая, в свою очередь, будет конвертировать определенные данные, и сравнивать результаты выполнения модифицированной программы с эталоном решения.
Возьмем для примера самый простой алгоритм для МТ. Увеличивающий бинарное число на единицу. Выглядит он так:
1q1->1q1R
0q1->0q1R
Bq1->Bq2L
1q2->0q2L
0q2->1q3L
Bq2->1STOP
0q3->0q3L
1q3->1q3L
Bq3->BSTOPR
Но нам его надо получить с помощью генетического алгоритма.
1. Генная инженерия
Для генетического алгоритма, построения программы Машина Тьюринга, нам потребуется. Придумать геном, из конечного множества вариаций хромосом. Которые будут состоять из определенного алфавита команд для машины Тьюринга.
- если символ «нуль»
- если символ «один»
- перейти к части кода №
- если символ отсутствует
- переместить каретку влево
- переместить каретку вправо
- затереть символ
- написать символ 0
- написать символ 1
- стоп программа
Разделим геном на отсеки, Хромосомы, каждой из них будет представлять позицию программы машины Тьюринга, и разделим хромосому на 3 отдельные части (так сказать на дополнительные хромосомы) соразмерно алфавиту машины и в каждой части закодируем действие необходимое выполнить машиной.
Три действия будут закодированы в двоичной системе:
- 1-й и 2-й знак кодируют символ, который нужно поставить в читаемый код.
В данном примере.
Символ отсутствует 00***
Нуль 01***
Единица 10***
- 3-й и 4-й знак кодирует номер хромосомы, к которой нужно перейти. Остановка программы
q1 **00*
q2 **01*
q3 **10*
STOP **11*
- 5-й знак кодирует в какую сторону передвинуть считывающий головку, над читаемым кодом.
R ****0
L ****1
И из этого мы имеем команду, в двоичном коде, размером в 5 бит.
Из выше перечисленного, геном будет состоять из трех хромосом, а те из 5х3=15 знаков.
Особь будет состоять из 15х3=45 знаков.
2. Подготовка «Чашки Петри»
Для реализации генерации алгоритма нам понадобится.
Генетический материал.
С генерированный программой генерации случайных строк бинарного кода.
Программа селекции.
Которая будет скрещивать, прошедший отбор генотипы.
Так сказать «Машина Тьюринга наоборот».
В которых будет хранится начальная «Бесконечная» лента и требуемый, после прохождения с генерированного генетическим алгоритмом генома, ее вариант.
Примеры лент:
Начальная лента — Конечный результат.
0001- 0010
0100- 0101
1011- 1100
Требование к «машине Тьюринга наоборот».
- Уметь читать и обрабатывать генетический материал.
- Сравнивать полученный результат на ленте, со своим эталоном результата, в процентах совпадения.
- Уметь выявлять геном не имеющий конечного результата.
- Уничтожать геном не прошедший проверку.
3. Генерация начальной популяции
Начальную популяцию генерировать из слов двоичного кода. в пять знаков, длиной в 9 слов для каждой особи.
4. Отбор популяции
Особи у которых процент совпадения ленты результата с эталонной лентой больше, проходят на селекцию видов.
Также при одинаковых результата. Выигрывает та особь, длина гена которой, короче другой.
5. скрещивание
селекция видов происходит обменом слов генома двух подвидов подошедшие к наибольшему проценту совпадения результата и эталона.
6. мутация
Неотъемлемая часть эволюции. В данном случае, происходит мутация отдельных слов представителя вида. Также мутация подразумевает добавление дополнительной хромосом, что не мало важно для решения более сложных задач. Добавление дополнительных слов в хромосомы с расширением алфавита МТ.
В случая увлечения алфавита, или хромосом, требуется указание в начале генома инструкции для МТ, правил чтения. Так как изменение количества хромосом и количество букв в алфавите, скажется на количество бит\ген в геноме.
7. итог
Теоретически, алгоритмы полученные таким видом будут самые компактные и эффективными.
А самое главное, понятные человеку.
Спасибо за внимание.
Это моя первая статья на Хабрахабе. Планирую перейти от теории к практике, с дальнейшим написанием статьи.
Комментарии (23)
kefirfromperm
22.02.2017 13:14+2Ваша проблема — отсутствие фундаментальных знаний. Вы верно плохо учились в школе.
Проблема остановки
cagami
22.02.2017 14:43+1можно поинтересоваться, где это в школьной программе проходят Теорию алгоритмов
если не ошибаюсь в школьной программе поверхностно дают понятие алгоритма на информатике(и то базовые понятия)
Я не исключаю, что тоже был плохим учеником.kefirfromperm
22.02.2017 15:05+2Да я приукрасил. Этим я как бы намекаю на школьный возраст автора. Тонкая ирония.
Zenitchik
22.02.2017 13:42Я правильно понял, что «хромосома» — это состояние машины, а выбор одной из трёх её частей — определяется символом под кареткой?
3-й и 4-й знак кодирует номер хромосомы, к которой нужно перейти. Остановка программы
q1 **00*
q2 **01*
q3 **10*
STOP **11*
Т.е. состояния всего три? Довольно слабая машина получается, но принцип понятен.
5-й знак кодирует в какую сторону передвинуть считывающий головку, над читаемым кодом.
R ****0
L ****1
А как быть, если каретку не нужно смещать?
belkov_k_v
22.02.2017 23:47Я правильно понял, что «хромосома» — это состояние машины, а выбор одной из трёх её частей — определяется символом под кареткой?
Да так и есть. Машина автоматически переходит к той части хромосомы, в соответствие с символом под кареткой.
допустим есть хромосома- 10011 10110 10011 под кареткой находится символ «1» или в понимание машины «10» в двоичном коде или 2 в десятичном и это говорит что машина должна выполнить третью часть (если считать и ноль за число) хромосомы.
Т.е. состояния всего три? Довольно слабая машина получается, но принцип понятен.
количество хромосом можно увеличить но также нужно будет увеличить резерв под эти нужды и заранее дать инструкции для МТ какая связка ген за что отвечает.
немножко другой вариант для примера.
STOP **000*
q1 **001*
q2 **010*
q3 **011*
q4 **100*
q5 **101*
А как быть, если каретку не нужно смещать?
все тоже самое как и предыдущем примере. просто добавив 1 ген
******00 стоять на месте
******01 на право
******10 на лево
спасибо за критику. наводит на мысли.
Zenitchik
23.02.2017 14:21STOP **000*
q1 **001*
q2 **010*
q3 **011*
q4 **100*
q5 **101*
Да, так определённо лучше. Код стал расширяемым.
Логично также любой несуществующий код (если хромосом меньше 2^n) считать за STOP.
******00 стоять на месте
******01 на право
******10 на лево
Хорошо.
А 11 трактовать так же, как 00.belkov_k_v
24.02.2017 15:51Хорошо.
А 11 трактовать так же, как 00.
да можно задать в инструкции такое правило.
kefirfromperm
22.02.2017 15:21+3Короче, по существу. Генерация алгоритмов при помощи генетических алгоритмов на 1й взгляд выглядит привлекательно, но на деле не работает. На этапе отбора мы неизбежно натыкаемся на две фундаментальные неразрешимые (доказано что неразрешимые) проблемы: проблема доказательства корректности алгоритма, проблема остановки, которая является частным случаем проблемы доказательства корректности алгоритма.
Чтобы решить является ли алгоритм корректным, мы должны скормить ему все возможные последовательности входных данных. Ну нету другого способа. Что, естественно, невозможно. В случае с классическим определением алгоритмов через машину Тьюринга или алгорифмы Маркова входные данные представляют собой счетную бесконечность. Ладно мы можем взять какой-то промежуток входных данных. Но это нам совершенно никак не гарантирует того, что за пределами этого промежутка алгоритм будет работать корректно. Ну и зачем нам такой алгоритм, если для каждой возможной последовательности данных мы уже рассчитали выходное значение?
А проблема остановки просто усложняет нам жизнь вопросом: сколько нам ждать пока сгенерированный алгоритм закончит работать? Ну и в ходе генерации мы получим массу промежуточных алгоритмов которые будут зацикливаться и съедать всё наше время.
Но даже в случае успеха на выходе вы получите кашу, разобраться в которой будет невозможно. Эволюция редко дает оптимальное решение.
И напоследок, рекомендую упражняться с алгорифмами Маркова.
Quilin
22.02.2017 15:29Никоим образом не отрицаю ваши аргументы, но! В общем случае генетические алгоритмы не обязаны выдавать стопроцентно правильный результат, они предназначены выдавать какой-то удовлетворительный результат. Конечно, в описанной задаче, когда у нас вообще-то имеется эталон решения, это не имеет никакого смысла, но если немножко перестроить задачу, например, в сторону «найти самый короткий/быстрый конечный автомат для эталона», то может быть оно и сканает. Конечно, проблема остановки остается открытой, и вероятно на достаточно больших эталонах и входных данных все наши автоматы будут вылетать по заданному таймауту, но отсутствие результата тоже результат, в конце концов.
PS: Под «коротким» я имел в виду только количество состояний.kefirfromperm
22.02.2017 16:38+1В общем случае генетические алгоритмы не обязаны выдавать стопроцентно правильный результат, они предназначены выдавать какой-то удовлетворительный результат.
Уверяю вас, в случае генерации алгоритма генетическим алгоритмом мы скорее всего получим алгоритм, который будет корректен ТОЛЬКО на тестовой выборке. Можно ли назвать такой результат удовлетворительным? Вряд ли.
Получить самый короткий алгоритм или конечный автомат тоже задача не очень хорошая для генетических алгоритмов. Эволюция плохо за собой убирается.Quilin
22.02.2017 16:52в случае генерации алгоритма генетическим алгоритмом мы скорее всего получим алгоритм, который будет корректен ТОЛЬКО на тестовой выборке
Я собственно сказал то же самое: имея тестовую выборку мы уже имеем решение задачи в самом точном виде. Если для ввода 00 вывод 0, а для 11 вывод 1, то ни один генетический алгоритм не скажет нам, это конъюнкция или дизъюнкция, я понимаю.
Но если для оценки успешности мы будем смотреть именно на то, как эволюция за собой убралась, разве она не начнет убираться?kefirfromperm
23.02.2017 09:04Надо попробовать. Но я думаю что гиблая затея. генетические алгоритмы меняют решение маленькими шагами, так что легко попасть в локальный минимум, из которого выбраться будет непросто.
lostmsu
22.02.2017 20:02Уверяю вас, в случае генерации алгоритма генетическим алгоритмом мы скорее всего получим алгоритм, который будет корректен ТОЛЬКО на тестовой выборке.
Имхо, это неверно. Оценочную функцию не обязательно реализовывать через сравнение результата с ожидаемым выходом из набора.
Например, можно оценить правильность работы алгоритма сортировки, подсчитав число инверсий в результате. Тогда можно входные данные генерировать случайно для каждого поколения. Те особи, которые не будут справляться с не встречавшимися ранее входными данными, очень быстро погибнут.
См. https://github.com/Church-of-the-Singularity/GeneticProgrammingkefirfromperm
23.02.2017 09:00В частном случае, да. В общем нет. Проблема доказательства корректности алгоритма никуда не девается.
SemmZemm
22.02.2017 23:56Наверное, всё же, Тьюринга в заголовке.
И хотелось бы увидеть прототип. Хоть и настроен несколько пессимистично, жду продолжения.
Shtucer
Ой, что-то в заголовке пошло не так.
devpony
Не только в заголовке..
Shtucer
О, да!
impwx
Мне больше всего понравился пассаж «машине Тьюренга на оборот».
Shtucer
А я вот не могу выбрать, всё прекрасное. Но мне обидно, что я никак не могу заставить себя вникать в суть статьи, она же там должна быть. Не зря же её из песочницы вынули.
Aristarkh
Мне нравится фраза «Размышления, о применение генетического алгоритма для Машина Тьюринга.»
FedyaShlyapkin
видимо текст статьи прошёл через машину Тьюринга