12.3. Вычислимость минимизации

Теорема 12.6. Пусть функция вычислима на МПД. Тогда вычислима и функция

.

Доказательство. Пусть G — программа стандартного вида, вычисляющая функцию G. Пусть . Построим программу F для вычисления функции F по следующему алгоритму: вычислять при Y = 0, 1, 2, … до тех пор, пока не найдется Y, такой, что , тогда Y будет требуемым выходом. Помещаем в регистры . Полагаем в начале Y = 0. Промежуточное значение помещаем в . Программа для вычисления F:

…

IP:

IQ:

Следовательно, функция F вычислима, что и требовалось доказать.

Следствие 12.6. Частично рекурсивные функции вычислимы на МПД, т. е. Ч Í Е.

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

Теорема 12.7. Всякая вычислимая на МПД функция является частично рекурсивной.

Доказательство. Пусть  — вычислимая на МПД функция и пусть P = I1I2…IS — соответствующая программа. Будем называть шагом вычисления выполнение одной команды программы. Для произвольных и определим следующие функции, связанные с вычислением :

Таким образом, , . Очевидно, что функции , всюду определены. Найдем теперь выражение для через введенные функции. Если значение определено, то останавливается после T0 шагов, где , поэтому . Если же значение не определено, то не останавливается, и тогда для любых , поэтому не определено. Следовательно, во всех случаях .

Теперь, если убедиться, что функции и частично рекурсивны, то таковой будет и функция . Ясно, что существует неформальный алгоритм вычисления значений функций и . Для этого нужно по заданным , T написать последовательность конфигураций K0 à K1 à … à KT и выписать содержимое регистра R1 и номер выполняемой на шаге T + 1 команды. По тезису Черча функции и частично рекурсивны и, значит, функция является частично рекурсивной, что и требовалось доказать.

Замечание 12.8. Более точный анализ показывает, что функции и являются примитивно-рекурсивными.

Следствие 12.9. Классы функций Ч и Е совпадают.

Рассмотрим теперь вопрос о соотношении введенных классов ЧПр, Ч0 и Ч.

Поскольку класс Ч содержит частично определенные функции, то ясно, что Ч0 Í Ч. Кроме того, очевидно, что ЧПр Í Ч0. Вопрос о том, является ли включение ЧПр Í Ч0 собственным решается несколько сложнее.

Первый пример общерекурсивной функции, не являющейся примитивно рекурсивной, был дан Аккерманом (1928).

Функция Аккермана задается соотношениями:

;

;

.

Можно доказать, что данные соотношения однозначно определяют функцию . Результаты вычислений убеждают, что имеется алгоритм вычисления функции .

В то же время доказывается, что функция не является примитивно рекурсивной, так как растет быстрее, чем любая одноместная примитивно рекурсивная функция. Доказательство, ввиду его громоздкости, опускается[6].

< Предыдущая		Следующая >