Онлайн 30.05 в 12:00 по мск

Пример:

7. Написать машину Тьюринга, которая вставляет после каждой буквы a букву b, если её там нет. Входные слова в

алфавите {a, b, c}. Можно расширять используемый алфавит.

8. Расширенная машина Тьюринга способна дополнительно выполнять команду вида: q, a → p, clearpos (стирание

ячеек ленты с положительными номерами, головка переходит в нулевую ячейку). Доказать, что любая вычислимая

на расширенной машине Тьюринга функция вычислима и на обычной.