Решение задач «1. Дано натуральное число n > 1. Напишите программу для машины...»,
Информатика в Новосибирске

1. Дано натуральное число n > 1. Напишите программу для машины Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, опишите словами, что выполняется машиной в каждом состоянии. 2. На ленте машины Тьюринга содержится последовательность символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, опишите словами, что выполняется машиной в каждом состоянии. 3. На ленте машины Тьюринга находится число, записанное в двоичной системе счисления. Заменить во входном слове все буквы 0 на 1 и наоборот. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. 4. На ленте машины Тьюринга содержится слово (последовательность символов), состоящее из символов {a, b}. Напишите программу для машины Тьюринга, которая удаляет из слова второй символ, если он есть. (Примечание: внутри выходного слова не должно быть пустых ячеек). Автомат в состоянии q1 находится над любым символом слова. Кроме самой программы-таблицы, опишите словами, что выполняется машиной в каждом состоянии. 5. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.