Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.

Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:

aaa —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

a —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

bbb —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

b —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

ab —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.

Результат обсуждения. Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q ₁ — движение по цепочке из букв “ a ”, а q ₂ — состояние движения по цепочке из букв “ b ”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q ₁ или q ₂, т.е. встретили a ₀, машина должна остановиться, мы обработали всю строку.

Рассмотрим следующие варианты входных слов:

bba —> abb

bbbaab —> aabbbb

aabbbaab —> aaaabbbb

Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: bba —> bbb —> вернуться к левому концу цепочки из букв “ b ” —> abb (заменить первую букву в этой цепочке на “ a ”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q ₂. Таким образом, для решения этой задачи нам нужно построить машину Тьюринга со следующими состояниями:

q ₁ — идем вправо по цепочке букв “ a ”. Если цепочка заканчивается a ₀, то переходим в q ₀; если заканчивается буквой “ b ”, то переходим в q ₂;

q ₂ — идем вправо по цепочке букв “ b ”, если цепочка заканчивается a ₀, то переходим в q ₀; если заканчивается “ a ”, то заменяем букву “ a ” на “ b ”, переходим в состояние q ₃(цепочку вида заменили на цепочку вида );

q ₃ — идем влево по цепочке букв “ b ” до ее левого конца. Если встретили a ₀ или “ a ”, то переходим в q ₄;

q ₄ — заменяем “ b ” на “ a ” и переходим в q ₁ (цепочку вида заменяем на цепочку вида .