Изменения

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

Навигация