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

ТЕОРЕМА 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.

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

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

Дата добавления: 2015-03-31