271
правка
Изменения
Нет описания правки
Рассмотрим множество [[Перечислимые_языки|перечислимых ]] языков <tex> RE </tex>.
{{Определение
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.
}}
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является разрешимым [[Разрешимые_(перечислиморекурсивные)_языки|разрешимым]].
}}
{{Теорема
|statement=
Никакое нетривиальное свойство языков не является разрешимым.
|proof=
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдем перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным).
Рассмотрим вспомогательную программу:
<tex>g_{i,x}(y):</tex>
if U(i, x) = 1
return <tex>p_X(y)</tex>
else
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i,x</tex>. Значит, можно рассмотреть такую программу:
<tex>
L(g_{i,x}) = \begin{cases}
X , & U(i, x) = 1 \\ \varnothing , & U(i, x) \neq 1 \\
\end{cases}
</tex>
Следовательно, <br/> <tex>
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}
p_A(p_X) , & U(i, x) = 1 \\ p_A(p_\varnothing ) , & U(i, x) \neq 1 \\
\end{cases} = \begin{cases}
1 , & U(i, x) = 1 \\ 0 , & U(i, x) \neq 1 \\
\end{cases}
</tex> {{- --}} программа, разрешающая универсальное множество. ПротиворечиеПолучили противоречие.
}}
