ОПРЕДЕЛЕНИЕ. Числовая функция f:Nk ® N вычисляется системой P, если " m1,

Числовая функция f:N^k ® N вычисляется системой P, если " m₁, ... , m_kÎ N(f(m₁, ... , m_k) = m_k+1 в системе P выводится слово “f( ₁, ... , _k) = _k+1“).

В качестве примера рассмотрим систему Поста, в которой вычисляется функция следования S(x) = x + 1.

Такая система имеет вид: P = (A, B, V, P), где
A = {0, 1, S, (, ), =}, B = {N}, V = {x, y}, а P - это следующие продукции.

1. Вспомогательные продукции, позволяющие выводить только правильные записи чисел из N в двоичной системе:

p₁: N 0, p₂: N1, p₃: N10, p₄: N 11,

p₅: , p₆: .

2. Продукция, задающая правило прибавления единицы к четным числам:

p₇: ;

3. Продукция, задающая правило прибавления единицы к нечётным числам (запись которых заканчивается единицей):

p₈: .

В частности, следующая последовательность образует вывод слова S(101) = 110:

1. N1 аксиома p₂;

2. N10 из N1 с помощью p₅;

3. N101 из N10 с помощью p₆;

4. S(10) = 11 из N10с помощью p₇;

5. S(101) = 110из N10и S(10) = 11 с помощью p_8.

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

Например, для вычисления функции p(x, y) = x + y достаточно добавить к уже имеющимся продукциям следующие новые продукции:

p₉: ; p₁₀: .

В продукции p₉ представлено правило прибавления к произвольному числу минимального неотрицательного целого числа.

В ₁₀ записано рекурсивное правило сложения двух произвольных чисел, использующего значение суммы первого числа и числа на единицу меньше, чем второе слагаемое.

Продукции p₉ и p₁₀ соответствуют рекурсивному определению функции p(x, y). Из них продукция p₉ задаёт граничное условие, а p₁₀ представляет рекурсивное правило, в котором значение p(x, y) выражается через значение p(x, v), где v = y - 1.

Используя продукции, позволяющие вычислять функции S и p, можно определять системы Поста, в которых вычисляются и другие функции.

Например, функция усеченной разности: d(x, y) = x -y вычисляется с помощью двух продукций, добавляемых к продукциям p₁ - p₁₀:

p₁₁ : , p₁₂ : .

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

Справедливость приведенного утверждения следует из теоремы 9.4.