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

Вычислимость рекурсии

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

Доказательство. Пусть G и Н — программы стандартного вида для вычисления функций g и h. Построим программу F, вычисляющую функцию . По начальной конфигурации по программе G вычисляется . Теперь, если y ¹ 0, то применяем (многократно) программу Н для нахождения , , …, . Положим . Запоминаем в регистрах . Номер цикла k, где k = 0, 1, …, y помещаем в . Промежуточное значение помещаем в . Программа F для вычисления f (здесь t =m+n):

T (1, m + 1)

…

T (n + 1, m + n + 1)

G [1, 2, …, n à m + n + 3]

I_q: J (t + 2, t + 1, p)

H [ m + 1, … m + n, t + 2, t + 3 à t + 3]

S (t + 2)

J (1, 1, q)

I_p: T (t + 3, 1)

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

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

.

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

…

I_p:

I_q:

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

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

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

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

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

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

Теперь, если убедиться, что функции и частично рекурсивны, то таковой будет и функция . Ясно, что существует неформальный алгоритм вычисления значений функций и . Для этого нужно по заданным , t написать последовательность конфигураций K ₀ à K ₁ à … à K_t и выписать содержимое регистра R ₁ и номер выполняемой на шаге t + 1 команды. По тезису Черча функции и частично рекурсивны и, значит, функция является частично рекурсивной, что и требовалось доказать.

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

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

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

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

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

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

;

;

.

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

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

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