Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Рекурсивные функции - часть 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.                   Случай а >.




Содержание  Назад  Вперед