Машина Тьюринга: исправление ошибки в слове «пороллилагромм»

В чем сложность-то? Если машины находится в начале или конце слова, то для решения задачи достаточно одного состояния. Машина должна на каждом шаге двигаться ко второму концу слова, если встречает символ "о", заменять его на "а", если встречает символ "а", заменять его на "о", если встречает символ "и", заменять его на "е". Если встречает пустую ячейку - останавливаться.

0