Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
aaa —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
a —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
bbb —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
b —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
ab —> выходное слово совпадает с входным, просматриваем входное слово до тех пор, пока оно не заканчивается.
Результат обсуждения. Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q 1 — движение по цепочке из букв “ a ”, а q 2 — состояние движения по цепочке из букв “ b ”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q 1 или q 2, т.е. встретили a 0, машина должна остановиться, мы обработали всю строку.
Рассмотрим следующие варианты входных слов:
bba —> abb
bbbaab —> aabbbb
aabbbaab —> aaaabbbb
Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: bba —> bbb —> вернуться к левому концу цепочки из букв “ b ” —> abb (заменить первую букву в этой цепочке на “ a ”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q 2. Таким образом, для решения этой задачи нам нужно построить машину Тьюринга со следующими состояниями:
q 1 — идем вправо по цепочке букв “ a ”. Если цепочка заканчивается a 0, то переходим в q 0; если заканчивается буквой “ b ”, то переходим в q 2;
q 2 — идем вправо по цепочке букв “ b ”, если цепочка заканчивается a 0, то переходим в q 0; если заканчивается “ a ”, то заменяем букву “ a ” на “ b ”, переходим в состояние q 3(цепочку вида 
заменили на цепочку вида 
);
q 3 — идем влево по цепочке букв “ b ” до ее левого конца. Если встретили a 0 или “ a ”, то переходим в q 4;
q 4 — заменяем “ b ” на “ a ” и переходим в q 1 (цепочку вида заменяем на цепочку вида 
.
