Доказательство окончено. Вспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованиемВспомогательные символы R и Q использованы для того, чтобы продукция, получаемая из продукции одной из систем описанным в доказательстве преобразованием, могла применяться только к таким совокупностям слов, которые выводятся с помощью преобразованных продукций той же системы. Если, например, при построении системы PU в качестве множества продукций для PU взять объединение множеств неизмененных продукций систем P 1 и P 2, то можно получить систему, в которой выводятся слова, не входящие в W 1 В качестве примера рассмотрим системы P 1 и P 2 со следующими совокупностями продукций: p1,1: 1, p1,2:
p2,1: 0, p2,2:
Тогда с помощью продукций (1) системы P 1 можно выводить слова, составленные только из единиц, а при помощи множества (2) системы P 2 - слова, которые имеют конечное число нулей. Однако продукции p1,1, p1,2, p2,1, p2,2, используемые совместно, позволяют выводить любые слова, состоящие из нулей и единиц. Семейство классов слов, выводимых в системах Поста, не замкнуто относительно операции взятия дополнений таких множеств. Это означает, что существует такая система P = (A, B, V, P), для которой множество A * \ WP не выводится ни в одной системе Поста. Доказательство этого факта будем приведено ниже после изучения связи множеств слов, выводимых в системах Поста и множества частично-рекурсивных функций.
Всякое множества W - таких слов в некотором основном алфавите A, что W и его дополнение до A * выводимы в некоторых системах Поста, является разрешимым. Справедливость последнего свойства вытекает из следующей теоремы.
|
W 2.
; (1)
. (2)
