Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Рекурсивные функции - часть 6
Поэтому нужно расширить его так, чтобы также могли быть описаны и частичные функции.
Пусть задана частичная функция
f: Nk+1 -> “N (k Î N).
Специфицируем частичную функцию
m(f): Nkà N
через
m(f)(x1, ..., xk) = min {у Î N : f(x1, ..., xk y) = 0},
если существует такое число у ÎN, что
f(x1, ..., xk, у) =0
и для всех z < у значение функции f (х1, ..., хk, z) определено. Если такого числа у не существует, то значение применения функции m(f) к аргументу (x1, ..., хn) не определено.
Здесь говорится о принципе минимизациию
Функционал
m: (Nл+1
-> N) -> (NkàN),
который в описанной выше форме каждую (k+1)-местную функцию отображает
на k-местную функцию, называется также m-оператором.
Функция m(f) очевидно вычислима, если функция f вычислима. Это можно обосновать следующим образом. Можно тривиальным образом вычислять последовательно значения f(x1, ..., xn, 0), f(x1, ..., xn, 1),... до тех пор, пока не получится значение 0 как результат. Тогда можно закончить вычисления с соответствующим значением у в качестве результата. Если не существует нулевого места или же один из исследуемых вызовов не завершается до того, как будет найдено нулевое место, то такой способ не завершается. В этом случае применение функции m (f) не определено. Функции, которые могут быть определены на основании примитивно-рекурсивных функций с дополнительным применением m-оператора, называются m-рекурсивными.
Пример (m-рекурсивные функции). Следующие функции являются m-рекурсивными:
(1) Частично определенное вычитание
а-Ь= [a-b, если а>Ь; не определено иначе.]
Определяется
а - b = m(hо)(а, b), где
ho:N3
-> N
есть примитивно-рекурсивная функция, специфицированная равенством
ho(a, b, у) = sub(b+y, a)+sub(a, b+y).
Здесь sub обозначает тотальное вычитание на натуральных числах
Sub(а,b)=[a-b, если а>b; sub(a,b)= 0 иначе]
m (ho) на самом деле есть искомая функция.
1. Случай а >.
