Изменения
Нет описания правки
== Определения ==
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm RE </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset RE </tex>.
}}
{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm RE </tex>.
}}
{{Определение
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>\mathrm RE \setminus A</tex>, которое также будет разрешимым и нетривиальным).
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.
