Доказательство окончено.

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

ФУНКЦИИ, ВЫЧИСЛЯЕМЫЕ СИСТЕМАМИ ПОСТА

Пусть P = (A, B, V, P) - система Поста, основной алфавит, который вместе с другими символами содержит символы f,), (и символ запятой -,. Здесь f - функциональный символ, обозначающий некоторую функцию.

ОПРЕДЕЛЕНИЕ

Словарная функция f: (A*) ⁿ ® A* вычисляется системой P, если: " ₁,..., _n Î A* (f ( ₁,..., _n) = _{n+ 1} в системе P выводится слово ″ f ( ₁,..., _n) = _{n+ 1}″),

То есть функция f, вычисляемая системой Поста P, отображает набор ( ₁,..., _n), составленный из - слов в алфавите A, в слово _{n+ 1} в том же алфавите тогда и только тогда, когда в P выводима запись: ″ f ( ₁,..., _n) = _{n+ 1}″.

Иначе говоря, в системе P выводятся записи таких слов, которые представляют график отображения f.

Аналогично определяется понятие числовой функции, вычисляемой в некоторой системе Поста P.

Пусть обозначает двоичную запись числа m.

ОПРЕДЕЛЕНИЕ

Числовая функция 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.

ТЕОРЕМА 9.4

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

Доказательство

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

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

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

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

.

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

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

f (x ₁,..., x_n), j₁(x _1,1,..., x _{1, m 1}),..., j _n (x_{n ,1},..., x_{n , m n}), которые вычисляются системами Поста P ₀, P ₁,..., P _n соответственно.

Покажем, что функция h (x_{i 1},..., x_{i k}) =

= f (j₁(x _1,1,..., x _{1, m 1}),..., j _n (x_{n ,1},..., x_{n , m n})),

где x_{i 1},..., x_{i k} - все различные переменные функций 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}) = m t (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.

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

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

Не нашли, что искали? Воспользуйтесь поиском: