Изменения

Перейти к: навигация, поиск

Свойства перечислимых языков. Теорема Успенского-Райса

Нет изменений в размере, 22:57, 26 ноября 2016
улучшено доказательство
Язык никакого нетривиального свойства <tex>A</tex> не является разрешимым.
|proof=
Приведём доказательство от противного.
Предположим, что <tex>A</tex> разрешимо.
 
Пусть <tex>p_\infty</tex> {{---}} всегда зацикливающийся алгоритм.
'''Рассмотрим случай, когда <tex>p_\infty \in L(A)</tex>.'''
 
Приведём доказательство от противного. Предположим, что <tex>A</tex> разрешимо.
Рассмотрим <tex>p_a</tex> {{---}} программу, такую что <tex>p_a \in L(\overline A)</tex> (такое <tex>p_a</tex> существует, т.к. <tex>A</tex> {{---}} нетривиально), а также произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.
129
правок

Навигация