Вычислимость суперпозиции

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

Доказательство. Пусть — программы стандартного вида для вычисления функций,, …,соответственно. Напишем программуН для вычисления h. Положим . Запомнимв регистрах, в регистрахзапоминаем значения, …,соответственно. Указанные регистры не затрагиваются вычислениями по программам. Теперь дадим программуР вычисления h:

…

…

.

Ясно: вычисление останавливается тогда и только тогда, когда заканчиваются вычисления каждой,и вычисление, что и требовалось доказать.

Следствие 12.4. Пусть — вычислимая на МПД функция и— последовательностьn переменных из (возможно с повторениями). Тогда функциявычислима.

Доказательство. Если , то, и потому функцияh — вычислима, что и требовалось доказать.

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

Теорема 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).

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

;

;

.

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

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

Л е к ц и я 13