Для заданной вычислимой функции в заданной системе счисления. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по программированию
Для заданной вычислимой функции в заданной системе счисления

Для заданной вычислимой функции в заданной системе счисления .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

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

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Выпишем для наглядности числа, меньшие 7 в четверичной кодировке:
0, 1, 2, 3, 10, 11, 12
Т.е., чтобы на выходе получить 1 требуется, чтобы входное слово состояло как минимум из двух разрядов, причем в случае двух разрядов – или первый слева разряд был равен не менее двум, или (если первый слева разряд равен 1) второй разряд был равен 3.
Словесное описание алгоритма:
Для определенности считаем, что каретка машины Тьюринга указывает на первую цифру числа x в четверичной кодировке.
Шаг 1. Если текущее число больше 1, стираем его, передвигаемся вправо и переходим на шаг 2 . Иначе – стираем его, передвигаемся вправо и переходим на шаг 4.
Шаг 2. Если обнаружен пустой символ (т.е. число состоит из одного разряда или равно 10, 11 и 12 – как будет показано далее), то пишем 1 завершаем работу алгоритма. Иначе (необходимо стереть все разряды числа и записать 0) стираем символ, перемещаемся вправо и переходим на шаг 3.
Шаг 3. Если обнаружен пустой символ, то пишем 0 и завершаем работу алгоритма, иначе – стираем символ, перемещаемся вправо и повторяем шаг 3.
Шаг 4. Если обнаружен пустой символ (т.е. число состоит из одного разряда), то пишем 1 завершаем работу алгоритма

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу