Изменения

Получили, что если <tex>n \in X</tex>, то <tex>Vn V_n \in L(\overline S)</tex>, а если <tex>n \notin X</tex>, то <tex>Vn V_n \in L(S)</tex>. Таким образом, <tex>n \in X \iff V_n \in L(\overline S)</tex>.

Так как <tex>\overline S</tex> - разрешимо, то можно проверить для любого <tex>a</tex>, лежит ли оно в <tex>\overline{S}</tex>. Но это тоже самое, что и проверка <tex>n \in X</tex>. Тогда можно для каждого <tex>n</tex> проверить , лежит ли оно в <tex>X</tex>, а следовательно и построить разрешитель для <tex>X</tex>. Так как <tex>X</tex> - неразрешимо, получили противоречие.

* Rice, H. G. "{{---}} Classes of Recursively Enumerable Sets and Their Decision Problems." {{---}} Trans. Amer. Math. Soc. 74, 358-366, 1953.* Хопкрофт Д., Мотванн Р., Ульманн Д. {{---}}Введение в теорию автоматов, языков и вычислений страница {{---}} стр. 397.[[Категория: Теория формальных языков]]