Условие задачи
Для заданной вычислимой функции в заданной системе счисления
a. Представить словесное описание вычисляющего функцию алгоритма, если исполнитель алгоритма может выполнять следующие действия:
i. находить начало и конец слова,
ii. передвигаться на один символ влево или вправо,
iii. стирать слово или символ в начале-конце слова,
iv. заменять текущий символ на другой символ алфавита,
v. печатать стандартное слово-результат «да», «нет», «верно» и т.п.
b. Составить вычисляющий алгоритм в одном из следующих исчислений: Машины Тьюринга/Нормальные алгоритмы Маркова.
c. Привести не менее трех различных примеров применения алгоритма из пункта b) к входным словам, дающих разные конечные результаты,
d. Для каждого входного слова-примера из пункта c) подсчитать количество потребовавшихся шагов алгоритма.
1. Функция равна 1, если аргумент меньше 7, и 0 в противном случае, кодировка четверичная,
Ответ
Выпишем для наглядности числа, меньшие 7 в четверичной кодировке:
0, 1, 2, 3, 10, 11, 12
Т.е., чтобы на выходе получить 1 требуется, чтобы входное слово состояло как минимум из двух разрядов, причем в случае двух разрядов или первый слева разряд был равен не менее двум, или (если первый слева разряд равен 1) второй разряд был равен 3.
Словесное описание алгоритма:
Для определенности считаем, что каретка машины Тьюринга указывает на первую цифру числа в четверичной кодировке.
Шаг 1. Если текущее число больше 1, стираем его, передвигаемся вправо и переходим на шаг 2. Иначе стираем его, передвигаемс...
