Изменения
Новая страница: «{{Определение |definition=Рассмотрим множество перечислимых языков <tex>RE</tex>. *Свойством языков н…»
{{Определение
|definition=Рассмотрим множество перечислимых языков <tex>RE</tex>.
*Свойством языков называется множество <tex>A \subset RE</tex>.
*Свойство <tex>A</tex> называется тривиальным, если <tex>A = \varnothing </tex> или <tex>A = RE</tex>.
*Языком свойства называется множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p | L(p) \in A \rbrace </tex>.
*Свойство <tex>A</tex> называется разрешимым (перечислимым), если <tex>L(A)</tex> разрешимо (перечислимо).
}}
{{Теорема
|statement=
Никакое нетривиальное свойство языков не является разрешимым.
|proof=
От противного. Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> - программа, разрешающая <tex>A</tex>.
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдем к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным).
В то же время, поскольку <tex>A</tex> непусто, найдется перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> - полуразрешитель <tex>X</tex>.
Рассмотрим вспомогательную программу:
<tex>g_{i,x}(y)</tex>
if U(i, x) = 1
return <tex>p_X(y)</tex>
else
зависнуть
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i,x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
return <tex>p_A ( g_{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(X) & U(i, x) = 1 \\
p_A(\varnothing ) & U(i, x) \neq 1 \\
\end{cases} = \begin{cases}
1 & U(i, x) = 1 \\
0 & U(i, x) \neq 1 \\
\end{cases}
</tex> - программа, разрешающая универсальное множество. Противоречие.
}}
|definition=Рассмотрим множество перечислимых языков <tex>RE</tex>.
*Свойством языков называется множество <tex>A \subset RE</tex>.
*Свойство <tex>A</tex> называется тривиальным, если <tex>A = \varnothing </tex> или <tex>A = RE</tex>.
*Языком свойства называется множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p | L(p) \in A \rbrace </tex>.
*Свойство <tex>A</tex> называется разрешимым (перечислимым), если <tex>L(A)</tex> разрешимо (перечислимо).
}}
{{Теорема
|statement=
Никакое нетривиальное свойство языков не является разрешимым.
|proof=
От противного. Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> - программа, разрешающая <tex>A</tex>.
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдем к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным).
В то же время, поскольку <tex>A</tex> непусто, найдется перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> - полуразрешитель <tex>X</tex>.
Рассмотрим вспомогательную программу:
<tex>g_{i,x}(y)</tex>
if U(i, x) = 1
return <tex>p_X(y)</tex>
else
зависнуть
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i,x</tex>. Значит, можно рассмотреть такую программу:
<tex>US(\langle i, x \rangle )</tex>
return <tex>p_A ( g_{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(X) & U(i, x) = 1 \\
p_A(\varnothing ) & U(i, x) \neq 1 \\
\end{cases} = \begin{cases}
1 & U(i, x) = 1 \\
0 & U(i, x) \neq 1 \\
\end{cases}
</tex> - программа, разрешающая универсальное множество. Противоречие.
}}
