ОПРЕДЕЛЕНИЕ. Числовая функция 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₂: N 1, p₃: N 10, p₄: N 11,

p₅: , p₆: .

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

p₇: ;

 

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

p₈: .

 

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

 

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

2. N 10 из N 1 с помощью p₅;

3. N 101 из N 10 с помощью p₆;

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

5. S (101) = 110 из N 10 и 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.