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