Упражнения

3.2. Составьте алгоритмы, вычисляющие функции:

а)

б)

в)

г)

д)^*

е)^*

Здесь [x / y] означает наименьшее целое число, не превосходящее действительное число x / y.

3.3. Покажите, что для каждой команды переадресации существует программа без команд переадресации, которая на всякой конфигурации МНР дает тот же результат, что и T(m, n). Это означает, что команды переадресации на самом деле избыточны в нашем определении МНР. Тем не менее, представляется естественным и удобным иметь такие команды, облегчающие построение алгоритмов.

Введем еще несколько понятий необходимых для дальнейшего изложения.

Определение 3.2. n–местным предикатом на множестве M называется отображение H, сопоставляющее каждому упорядоченному набору (a₁, a₂, ..., a_n) элементов из M одно из логических значений «истинно» или «ложно».

Пример 3.4. Функции «быть простым числом», «быть четным числом» являются одноместными предикатами на множестве целых чисел.

Пример 3.5. Свойства «иметь одинаковые остатки при делении на 3» или «быть равными» являются бинарными предикатами на множестве целых чисел.

Определение 3.3. Предикат называется разрешимым, если его характеристическая функция

вычислима.

В контексте вычислимости предикаты часто называют проблемами. Поэтому ниже мы наряду с термином «разрешимый предикат» будем использовать также «разрешимая проблема».