Задача по машине Тьюринга.

Машина Тьюринга определяется, в первую очередь своим алфавитом, т. е. множеством символов, которые она может записывать в ячейки своей ленты:
1. Пустой символ, обозначим его буквой П
2. Цифры от 0 до 9
3. МеткаПусть будет символ *.

Дальше нужно определиться с начальным состоянием. В данной задачи для определенности (и удобства) можно предположить, что все метки находятся справа от считывающе-записывающей головки. Иначе алгоритм может быть бесконечный )) Ну, и для простоты предположим, что в начальный момент головка стоит на пустой клетке (хотя потом не сложно будет доработать алгоритм так, чтобы он работал и в случае, если головка стоит на заполненных метками клетках".

Основная идея алгоритма - находить первую метку, менять ее на пустой символ, возвращаться назад и увеличивать на 1 значение счетчика. Справа это так удобно делать :-)

Теперь нужно определиться с набором состояний. Во-первых, нам нужно находить первую метку. Пусть режим поиска метки будет состоянием А. Поиск младшего разряда нашего счетчика - состояние Б. Потом нужен режим увеличения счетчика на 1 - это состояние В. Еще нужен режим остановки К и начальный режим Н.

Следующий шаг создания машины - разработка алгоритма. Это список вида Xi->YjZ Где X - исходное состояние, i- символ в текущей ячейке, Y - состояние в которое переходит машина, j-символ, который будет записан в ячейку, Z - перемещение (R-шаг вправо, L-шаг влево, N-оставаться на месте)

В начальный момент машина будет находиться в состоянии Н. И сперва нам нужно пометить место, где будут храниться разряд единиц нашего счетчика:
НП -> А0R (Если машина находится в начальном состоянии на пустой ячейке, то переходим в состояние А, записываем в ячейку цифру 0 и делаем шаг вправо.

Для поиска первой метки будет что-то вот такое:
АП -> АПR (Если машина находится в состоянии А и стоит на пустой клетке - нужно оставить клетку пустой, оставить состояние А и сделат шаг вправо)

Как только достигнем первой метки, нужно сменить состояние:
А* -> БПL (если в состоянии А в ячейке стоит метка, то меняем состояние на Б, стираем метку и делаем шаг влево)

Теперь нужно найти, где хранится младший разряд нашего счетчика:
БП -> БПL (в состоянии Б если ячейка пуста - делаем шаг влево)

Самое интересное - увеличение счетчика на 1 оставляю для самостоятельной работы. Идея очевидна - перейти в состояние В, увеличивать очередной разряд на 1, и при достижении 9 выполнить перенос разряда в следующую позицию справа. После чего вернуться в состояние А.

Ах, да чтобы алгоритм остановился нужно предпринять специальные меры. Я вижу такой вариант добавить еще одно состояние и набор правил, которые в начале алгоритма заставят головку дойти до последней метки и за ней поставить стоп-символ, например 9. И в состоянии А добавить правило
А9 -> К9N (если в режиме А встретили стоп-символ, то переходим в конечное состояние).

Как-то так, наверное :-)

Сделай банальный счётчик и прибавляй один с каждым символом.