И их вычислимость

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

Л е к ц и я 12

Приведем еще один класс вычислимых функций, предложенный в 30-х годах XX века (Гедель, Клини, Черч) в качестве уточнения понятия алгоритма — класс частично рекурсивных функций. Данный класс определяется путем указания конкретных исходных функций и фиксированного множества операций получения новых функций из заданных. Ниже рассматриваются функции типа .

В качестве базисных функций берутся следующие:

нуль-функция: ;

функция следования: ;

функции выбора аргументов:

;

допустимыми операциями над функциями являются операции суперпозиции (подстановки), рекурсии и минимизации.

Операция суперпозиции. Пусть даны n -местная функция g и n функций . Считаем, что функции зависят от одних и тех же переменных . Это можно сделать путем введения фиктивных переменных. Суперпозицией (подстановкой) функций g и называется функция

.

Если среди заданных функций имеются частичные, то и функция h будет частичной. Функция h на наборе переменных определена тогда и только тогда, когда определены все функции и функция g определена на наборе . Операцию суперпозиции обозначают .

Операция рекурсии (точнее: примитивной рекурсии). Пусть заданы n -местная функция и (n + 2)-местная функция . Определим (n + 1)-местную функцию f индуктивным образом с помощью соотношений:

;

.

Ясно, что данные соотношения однозначно определяют функцию f. Если функции g и h частичные, то считается определенной в том и только в том случае, когда определены и при . Значит, если не определено, то и не определено при . Про функцию f говорят, что она получена рекурсией из функций g и h и обозначают f = R (g, h).

Операция минимизации. Пусть задана n -местная функция . Зафиксируем набор и рассмотрим уравнение относительно y: . Будем решать данное уравнение, вычисляя последовательно , , , …, и сравнивая с . Наименьшее y, для которого выполнено исходное уравнение обозначим через . При этом считаем, что y определено, если определено при всех . В противном случае считаем, что y не определено. Значение y есть функция f от переменных , про которую говорят, что она получена из функции g операцией минимизации и обозначают . Заметим, что определенные выше операции S и R, будучи примененными к всюду определенным функциям, дают всюду определенные функции. Операция М может давать частичные функции даже при применении к всюду определенным функциям.

Пример 12.1. . Здесь всюду определена, но определена только при .

Дадим теперь основное определение данного раздела.

Определение 12.2. Функция называется частично рекурсивной, если она может быть получена из базисных функций применением конечного числа раз операций суперпозиции, рекурсии и минимизации. Иногда частично рекурсивные функции называют функциями, вычислимыми по Черчу. Всюду определенная частично рекурсивная функция называется общерекурсивной. Если рассматривать тот же базис функций, но в качестве допустимых операций брать операции суперпозиции и рекурсии, то получаемые функции называются примитивно-рекурсивными.

Обозначим: Ч — класс частично рекурсивных функций, Ч ₀ — класс общерекурсивных функций, Ч _пр — класс примитивно-рекурсивных функций.

Класс частично рекурсивных функций — одно из главных понятий теории алгоритмов. Это объясняется тем, что какие бы классы точно очерченных «алгоритмов» до сих пор не рассматривались, во всех случаях оказывалось, что соответствующие числовые функции, вычислимые посредством алгоритмов этих классов, были частично рекурсивными. Поэтому общепринятой является гипотеза, формулируемая как Тезис Черча (для частично рекурсивных функций). Класс алгоритмически вычислимых функций совпадает с классом всех частично рекурсивных функций. Принятие данного тезиса позволяет истолковывать доказательство, что некоторая функция не является частично рекурсивной, как доказательство отсутствия алгоритма вычисления ее значений.

Сделаем одно замечание. Пусть необходимо доказать, что конкретная функция вычислима. Это можно сделать следующими способами:

1) написать программу машины Тьюринга или МПД, вычисляющую f, либо показать, что f принадлежит классу функций, вычислимость которых доказана;

2) написать рекурсивную схему для f, показывающую, что f — частично рекурсивна;

3) дать неформальное (но достаточно точное) описание алгоритма, вычисляющего f, и затем сослаться на тезис Черча.

Мы будем пользоваться способом 3 как строгим методом доказательства, основанным на тезисе Черча.

Приведем примеры частично рекурсивных функций и установим частичную рекурсивность основных числовых функций, используемых в арифметике и анализе.

1. Функции-константы. .

2. Функция . Имеем , . Это есть рекурсия с помощью функций и .

3. Функция . Имеем , . Это есть рекурсия с помощью функций , .

4. Функция . Имеем , . Это есть рекурсия с помощью функций , .

5. Функция Имеем , . Это рекурсия, в которой , .

6. Функция Имеем , . Это рекурсия, в которой , .

7. Функция Имеем , . Это рекурсия, в которой , .

8. Функция Имеем , . Это рекурсия, в которой , .

9. Функция . Имеем . Отметим, что поскольку функция общерекурсивна, то можно заменить определение операции минимизации, рассматривая вместо функции вида , где . Определяемый класс функций при этом будет тем же самым.

10. Функция . Имеем .

11. Функция . Имеем .

12. Функция — целая часть от деления x на y. По определению полагаем , чтобы фукнция была всюду определена. Имеем . Действительно, при y = 0 .

При существует минимальное z, , при котором или или , откуда .

13. Функция — остаток от деления x на y. Имеем .

14. Функция

Имеем .

15. Двоичная степень числа x. , если , но не выполняется . Имеем и замечаем, что функция — общерекурсивна.

16. Функция, отличная от 0 в конечном числе точек. Если в точках , причем , то имеем .

Аналогично можно доказать (примитивную) рекурсивность функций:

число простых чисел, не превосходящих x;

— квадратичный остаток числа x;

— -е простое число (, , , , и т.д.).

Покажем теперь вычислимость на МПД частично рекурсивных функций.

Базисные функции o (n), s (n), вычислимы на МПД командами Z (n), S (n), T (m, 1).

Дата добавления: 2014-12-29