Изменения
→Перечислимое неразрешимое множество
===Перечислимое неразрешимое множество===
{{Теорема
|statement=
Существует перечислимое неразрешимое множество
|proof=
Возьмем вычислимую функцию <tex>f(x)</tex> не имеющую всюду определенного вычислимого продолжения. Тогда область определения <tex>F</tex> этой функции будет искомым множеством. Действительно, <tex>F</tex> [[Перечислимые языки|перечислимо]]. Предположим, что <tex>F</tex> разрешимо. Но тогда функция <tex>g(x)</tex> равная <tex>f(x)</tex> при <tex> x \in F </tex> и равная <tex>0</tex> если <tex> x \notin F </tex> является вычислимым всюду определенным продолжением функции <tex>f</tex>. Пришли к противоречию, значит <tex>F</tex> неразрешимо.
}}
===Главная нумерация===
