Доказательство. Приведем описание процедуры, позволяющей распознавать слова, содержащиеся во множестве W.
Приведем описание процедуры, позволяющей распознавать слова, содержащиеся во множестве W.
Воспользуемся двумя экземплярами алгоритма построения всех конечных выводов в произвольных системах Поста.
С помощью первого из этих алгоритмов будем строить все такие выводы в системе P1, а с помощью второго - все выводы в системе P2.
Такие два параллельно работающих алгоритма позволяют последовательно выводить все слова из множеств W и A* \W.
Поскольку произвольное 
A* содержится либо во множестве W, либо в дополнении этого множества, то 
содержится либо в выводах системы P1, либо в выводах системы P2.
В первом случае Î W. Во втором случае Î A* \W.
Поэтому для любого Î A* за конечное число шагов работы приведенного алгоритма устанавливается принадлежность множеству W. Значит, множество W является разрешимым.
Дата добавления: 2015-09-18; просмотров: 449;