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

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

1. Покажем, что все примитивные функциивычисляются системами Поста.

Действительно, функция O(x) вычисляется с помощью продукции p: , добавленной к рассмотренным ранее продукциям p₁ - p₆, позволяющим выводить все правильные двоичные записи натуральных чисел.

Функция S(x) вычисляется с помощью продукций p₁ - p₈, а (x₁, . . . , x_n) вычисляется с помощью дополнительной продукции

.

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

Пусть заданы функции

f(x₁, . . . , x_n), j₁(x_1,1, . . . , x_1,m1), . . . , j_n(x_n,1, . . . , x_n,mn), которые вычисляются системами Поста P₀, P₁, . . . , P_n соответственно.

Покажем, что функция h(x_i1, ... , x_ik) =

= f(j₁(x_1,1, . . . , x_1,m1), . . . , j_n(x_n,1, . . . , x_n,mn)),

где x_i1, . . . , x_ik- все различные переменные функций j₁, . . . , j_n, также вычислима некоторой системой Поста.

Обозначим как G₀, G₁, . . . , G_n - вспомогательные символы, которые не встречаются среди символов алфавитов систем Поста P₀, P₁, . . . , P_n.

Модифицируем продукции этих систем Поста, приписав всем образцам каждой продукции из P_iслева символ G_i.

Рассмотрим систему Поста P, продукциями которой являются все модифицированные продукции систем P₀, P₁, . . . , P_n, а также продукция

.

Очевидно, что Pвычисляет функцию h.

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

Пусть функция f выражается через функции g и h с помощью операции примитивной рекурсии

f(x₁, ... , x_n, 0) = g(x₁, ... , x_n)

f(x₁, ... , x_n, y + 1) = h(x₁, ... , x_n, f(x₁, ... , x_n, y)).

Пусть функции g и h вычисляются системами Поста P_g и P_h.

Возьмем два вспомогательных символа G_g и G_h, не встречающиеся среди символов алфавитов систем P_g и P_h.

Модифицируем продукции систем P_g и P_h, приписывая всем образцам в них слева соответственно символы G_g и G_h.

Рассмотрим систему Поста P_f, в которую включим модифицированные продукции систем P_g и P_h, продукции системы, вычисляющей функцию S(x) = x + 1, помеченные еще одним вспомогательным символом Gs. Для этого символа также предполагаем, что он не встречается среди символов всех рассматриваемых систем Поста.

Добавим к этим продукциям еще две

; (1)

(2).

Нетрудно видеть, что такие продукции соответствуют соотношениям схемы примитивной рекурсии, а P_f вычисляет функцию f.

4. Покажем, что если функция f выражается через функцию, вычислимую некоторой системой Поста, с помощью операции минимизации, то она также вычисляется некоторой системой Поста.

Пусть f(x₁, . . . , x_n+1) = mt(g(x₁, . . . , x_n, t) = x_n+1) и функция g(x₁, . . . , x_n+1) вычисляется продукционной системой P_g. Построим систему Поста P_f, которая вычисляет
f(x₁, . . . , x_n+1).

Включим в P_f продукции систем, вычисляющих функции S(x) и g(x₁, ... , x_n+1), а также добавим к ним продукции такой системы Поста, в которой выводятся пары неравных целых неотрицательных чисел: x <> y. Построение такой системы предлагалось ранее в упражнении.

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

Добавим к указанным продукциям новые продукции:

(1)

(2)

; (3)

.(4)

Эти продукции позволяют вычислять вспомогательную функцию , которая принимает значение 0 только для такого наименьшего значения t, при котором
g (x₁, ... , x_n, t) = x_n+1 и все значения g(x₁, ... , x_n, i) для i < t являются определенными.

Для вычисления значений функции f используются следующие две продукции:

; (5)

. (6)

Построенная система Поста вычисляет функцию f .

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

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