Доказательство окончено. Вспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованием

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

Если, например, при построении системы P_U в качестве множества продукций для P_U взять объединение множеств неизмененных продукций систем P ₁ и P ₂, то можно получить систему, в которой выводятся слова, не входящие в W ₁ W ₂.

В качестве примера рассмотрим системы P ₁ и P ₂ со следующими совокупностями продукций:

p_1,1: 1, p_1,2: ; (1)

p_2,1: 0, p_2,2: . (2)

Тогда с помощью продукций (1) системы P ₁ можно выводить слова, составленные только из единиц, а при помощи множества (2) системы P ₂ - слова, которые имеют конечное число нулей.

Однако продукции p_1,1, p_{1, 2}, p_2,1, p_2,2, используемые совместно, позволяют выводить любые слова, состоящие из нулей и единиц.

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

Это означает, что существует такая система P = (A, B, V, P), для которой множество A * \ W_P не выводится ни в одной системе Поста. Доказательство этого факта будем приведено ниже после изучения связи множеств слов, выводимых в системах Поста и множества частично-рекурсивных функций.

Всякое множества W - таких слов в некотором основном алфавите A, что W и его дополнение до A * выводимы в некоторых системах Поста, является разрешимым.

Справедливость последнего свойства вытекает из следующей теоремы.

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