Не торопитесь. Всему своё время. Подробнее об этой ветке форума в задании №6 второго этапа

Добавлено (19.02.2010, 18:52)
---------------------------------------------
Предлогаю решить вот такую задачу.

Входное слово состоит из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части входного слова. Автомат (каретка) в начальном состоянии обозревает крайний левый символ входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

У меня получилось. Надеюсь, что у вас тоже получится!

Задача:
Дано натуральное число n> 1, представленное в десятичной системе счисления. Автомат (каретка) в начальном состоянии обозревает самый правый символ входного слова. Необходимо построить машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “1000”, то выходным словом должно быть “999”, а не “0999”. Конечное положение автомата роли не играет. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Интересно, как ты думаешь, Снусмумрик, нам придется решать задачи друг друга или еще кто-нибудь появится?

Пример возможного начального положения:
_ 7 4 3 _ 6 0

Пример возможного итогового положения:
_ 8 5 4 _ 5 1

Дано входное слово, состоящее из цифр, разбитое пустой ячейкой на две части. Каретка стоит на самом левом символе входного слова. Построить Машину Тьюринга, которая левую часть увеличивает на 1, а правую уменьшает на 1; причем цифры 0 всегда увеличивать на 1, а цифры 9 всегда уменьшать на 1. После последнего правого символа входного слова поставить восклицательный знак.