Задача с машиной Тьюринга
На ленте машины Тьюринга расположен массив из N единиц. Построить машину Тьюринга, которая располагает этот массив на ленте так, чтобы все N единиц отделялись между собой одной пустой ячейкой. Машина находится в крайнем левом положении.
По дате
По рейтингу
123456789101112
q0,1 -> q1,пусто,R
q0,* -> q3,пусто,R
q0,пусто -> q2,1,L
q1,1 -> q1,1,R
q1,* -> q1,*,R
q1,пусто -> q0,*,R
q2,1 -> q2,1,L
q2,* -> q2,*,L
q2,пусто -> q0,пусто,R
q3,1 -> q3,1,R
q3,* -> q3,пусто,R
q3,пусто -> стоп Пока левый символ - '1', стираем эту '1' слева и приписываем '*','1' справа.
Как только левым символом оказывается '*' (т.е. все единицы разделены звёздочками), стираем все '*' и заканчиваем работу.
12345
111
11*1
1*1*1
*1*1*1
1 1 1 Перемести 1 вправо на 2 ячейки.
Пропусти одну ячейку и повторяй.
Остановись, если все единицы перемещены.
