Математическая логика и теория алгоритмов

2.6 Частично рекурсивные функции

назад | оглавление | вперёд

 

       С помощью операций суперпозиции и примитивной рекурсии из простейших функций получаются только полностью определенные функции. Введем еще одну операцию – операцию минимизации функции.

       Пусть имеется арифметическая функция f(x1,...,xn) (возможно частично определенная). Пусть существует какой-то механизм вычисления этой функции, причем значение функции не определено тогда и только тогда, когда этот механизм работает бесконечно, не выдавая никакого определенного результата.

       Фиксируем произвольный набор значений x1,...,xn-1 для первых n-1 аргументов функции f и рассмотрим уравнение относительно y : f(x1,...,xn-1,y)=xn.

       Чтобы найти натуральное решение y этого уравнения, будем вычислять при помощи указанного выше "механизма" последовательно значения f(x1,...,xn-1,a) для a=0,1,2,... и сравнивать с xn. Наименьшее значение a, для которого получится f(x1,...,xn-1,a)=xn, обозначим . Очевидно, что является n-арной частичной функцией, которая получена операцией минимизации из функции f(x1,...,xn).
       Описанный процесс нахождения y, будет продолжаться бесконечно в следующих случаях:

       Во всех этих случаях значение считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение y = a для уравнения f(x1,...,xn-1,y) = xn.

Предложение (Свойство операции минимизации). Операция минимизации сохраняет интуитивную вычислимость функций.
Доказательство.Пусть необходимо вычислить значение функции на наборе (x1,...,xn) для некоторой интуитивно вычислимой функции f. Применим процедуру вычисления функции f на наборе (x1,...,xn-1,0). Если через конечное число шагов процедура определяет значение f(x1,...,xn-1,0) и f(x1,...,xn-1,0)=xn , то полагаем значение функции равным 0. Если же f(x1,...,xn-1,0) ≠ xn, то переходим к следующему этапу, на котором применяем процедуру вычисления функции f на наборе (x1,...,xn-1,1) и т.д.
       Если на (t+1)-ом этапе вычислено значение функции f(x1,...,xn-1,t) и f(x1,...,xn-1,t)=xn, то полагаем значение функции равным t. Если на (t+1)-ом этапе вычислено значение функции f(x1,...,xn-1,t) и f(x1,...,xn-1,t) ≠ xn, то переходим к следующему этапу и т.д.
       В случаях, когда на каком-то этапе процедура вычисления функции f работает бесконечно или работа процедуры завершилась безрезультатно, то считаем функцию неопределённой на наборе (x1,...,xn). А так как описанная процедура пригодна для любого набора (x1,...,xn), то, очевидно, она представляет собой алгоритм вычисления значений функции .
        Предложение доказано.

       Процесс вычисления , описанный выше, показывает, что если функция f интуитивно вычислима, то значение (если оно существует) может быть вычислено эффективно.

       Приведем некоторые определения:

       Pассмотрим 3 примерa общерекурсивных функций:

Пример 1.Простейшие функции S(x), O(x), Umn(x1,...,xn) для n ≥ m всюду определены, поэтому они являются общерекурсивными функциями.

Пример 2.Все примитивно рекурсивные функции являются общерекурсивными функциями.

Пример 3.Минимизируем примитивно рекурсивную функцию
       
       Составим минимизирующее уравнение .
       Найдем значения функции g(x) при различных значениях x.
       При x = 0 нужно найти минимальное значение y, которое удовлетворяет условию f(y) = x = 0.

       При x = 1 нужно найти минимальное значение y, которое удовлетворяет условию f(y) = x = 1.        При x = 2 нужно найти минимальное значение y, которое удовлетворяет условию f(y) = x = 2.        Для остальных x > 2 . Получили, что функция g(x) всюду определена и имеет следующий вид:
       

       Далее рассмотрим 4 примерa частично рекурсивных функций:

Пример 1.Функция f(x,y)=y-x является частично рекурсивной, поскольку может быть получена с помощью операции минимизации из примитивно рекурсивной функции сложения. Действительно, . При y < x функция не определена.

Пример 2.Рассмотрим функцию, заданную уравнением:
       
       Результат операции минимизации не определен даже для точки х=0. Действительно, при x=0 нужно найти минимальное значение z, которое удовлетворяет условию z+0+1=0. Очевидно, что среди неотрицательных целых чисел такое z не существует. Таким образом, функция f(x) является частично рекурсивной функцией, которая нигде не определена.

Пример 3.Рассмотрим функцию, заданную следующим образом:
       
       Найдем значение f(0). При x=0 нужно найти минимальное значение z, которое удовлетворяет условию z+0=0. Очевидно, что такое z существует и z=0. Для x > 0 результат операции минимизации не определен, поскольку подбор нужного значения z никогда не будет закончен.

Пример 4.Минимизируем функцию .
       Уравнение, определяющее новую функцию выглядит так:
       
       Поскольку функция f(x) принимает только 3 значения (2,4,3), то функция g(x) определена только при этих значениях, в остальных точках значение функции g(x) не определено. Найдем значение g(2). Решая уравнение последовательной подстановкой, находим, что первое удовлетворяющее уравнению значение равно 5, т.е. g(2)=5. Аналогично определяем, что g(4)=6, g(3)=0. Таким образом,
       

       Обозначим KПРФ – множество всех примитивно рекурсивных функций, KЧРФ – множество всех частично рекурсивных функций, KОРФ – множество всех общерекурсивных функций, а KВФ – множество всех интуитивно вычислимых функций.
       Связь между этими множествами функций показывает следующее.

Предложение(о иерархии классов рекурсивных функций). .
Доказательство.Первое включение следует из определений примитивной рекурсивности и общерекурсивности функций. Существуют примеры общерекурсивных, но не примитивно рекурсивных функций (примеры не приводятся из-за сложности и громоздкости), поэтому включение строгое. Из определений частичной рекурсивности и общерекурсивности функций следует, что . Выше был приведен пример нигде не определённой частично рекурсивной функцией, а любая общерекурсивная функция является всюду определённой. Таким образом, имеет место строгое включение .
       Очевидно, что , т.е. любая частично рекурсивная функция интуитивно вычислима.
       Сделаем два важных замечания:

       Предложение доказано.


назад | оглавление | вперёд