Теорема 9.3

Пусть   такое множество слов в основном алфавите A, что множества слов  и A* \  выводятся в системах Поста ₁ и ₂.

Тогда существует алгоритм, который по любому слову A* за конечное число шагов работы определяет принадлежность множеству .

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

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

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

С помощью первого из этих алгоритмов будем строить все такие выводы в системе ₁, а с помощью второго  все выводы в системе ₂.

Такие два параллельно работающих алгоритма позволяют последовательно выводить все слова из множеств  и A* \ .

Поскольку произвольное A* содержится либо во множестве , либо в дополнении этого множества, то содержится либо в выводах системы _1, либо в выводах системы ₂.

В первом случае  . Во втором случае  A* \ .

Поэтому для любого  A* за конечное число шагов работы приведенного алгоритма устанавливается принадлежность множеству . Значит, множество  является разрешимым.

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

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

9.7. Функции, вычисляемые системами поста

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

Определение

Словарная функция f:(A*)ⁿ  A* вычисляется системой , если:  ₁, . . . , _n  A* (f( ₁, ... , _n) = _n+1 в системе  выводится слово ″f( ₁, ... , _n) = _n+1″),

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

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

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

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

ОПРЕДЕЛЕНИЕ

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

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

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

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

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

₅: , ₆: .

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

₇: ;

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

₈: .

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

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

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

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

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

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

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

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

₉: ; ₁₀: .

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

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

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

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

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

₁₁ : , ₁₂ : .

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

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

ТЕОРЕМА 9.4

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

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

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

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

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

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

.

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

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

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

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

= f(₁(x_1,1, . . . , x_1,m1), . . . , _n(x_n,1, . . . , x_n,mn)),

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

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

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

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

.

Очевидно, что  вычисляет функцию 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 вычисляются системами Поста _g и _h.

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

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

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

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

; (1)

(2).

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

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

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

Включим в _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 .

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

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

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

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

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

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

Теорема 9.5. Существует система Поста  = (A,B,V,P), такая что множество (AB)^* \ _ не является множеством слов выводимых в системах Поста.

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

Пусть U(n, x) универсальная частично рекурсивная функция для множества всех одноместных частично рекурсивных функций, определенная в главе 8. Рассмотрим вспомогательную функцию:

Поскольку функция h является вычислимой, то существует вычисляющая h система Поста П_h = (A_h, B_h, V_h, P_h), и не существует системы Поста П_H = (A_H, B_H, V_H, P_H), такой что A_h = A_H и = (A_h)* \ .

Последнее утверждение является верным, поскольку существование системы П_H влечет разрешимость множества A₁={(n, x)значение f_n(x) определено}, определенного в главе 8. Характеристическую функцию этого множества можно вычислять с помощью следующего алгоритма:

1. Пусть требуется определить принадлежность элемента множеству (n, x) A₁.

2. С помощью алгоритмом построения всех конечных выводов в произвольных системах Поста организуем последовательное заполнение множеств и .

3. Продолжаем процесс до тех пор, пока или не будет включено слово h(n, x) = 1.

4. Если слово h(n, x) = 1 добавляется во множество , то (n, x) A₁. Если слово h(n, x) = 1 добавляется во множество , то (n, x) A₁.

Поскольку слово h(n, x) = 1 обязательно выводится в одной из систем Поста или , то приведенная процедура за конечное число шагов определяет принадлежность произвольной пары (n, x) множеству A₁.

Теорема доказана.

266