Доказательство. Пусть W - такое множество слов в основном алфавите A, что множества слов W и A* W выводятся в системах Поста P1 и P2

ТЕОРЕМА 9.3

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

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

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

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

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

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

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

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

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

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