Изменения

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

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

Нет изменений в размере, 12:25, 13 декабря 2014
Теорема Успенского-Райса
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex> \mathrm {RE} \setminus A</tex>, которое также будет разрешимым и нетривиальным, так как <tex> \mathrm {RE} \setminus A</tex> != <tex>\varnothing </tex> и <tex> \mathrm {RE} \setminus A</tex> != <tex>\mathrm {RE} ) </tex>. Исключение пустого множества нам нужно чтобы различать <tex> X</tex> и пустое (при построении функции <tex>L(g_{i,x}))</tex>).
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.
Анонимный участник

Навигация