Задача с машиной Тьюринга

Question

Задача с машиной Тьюринга

мудрик Ученик (91), на голосовании 1 день назад

На ленте машины Тьюринга расположен массив из N единиц. Построить машину Тьюринга, которая располагает этот массив на ленте так, чтобы все N единиц отделялись между собой одной пустой ячейкой. Машина находится в крайнем левом положении.

Answer 1

Перемести 1 вправо на 2 ячейки.
Пропусти одну ячейку и повторяй.
Остановись, если все единицы перемещены.

Answer 2

 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' справа.
Как только левым символом оказывается '*' (т.е. все единицы разделены звёздочками), стираем все '*' и заканчиваем работу.