3622
правки
Изменения
успенский и райс
<tex> A </tex> {{---}} разрешимое семейство языков.
<tex> L_A </tex> {{---}} язык свойства языковмножество программ, удовлетворяющих св-ву <tex> A </tex>. Допустим, что он разрешимпустой язык <tex> \varnothing </tex> принадлежит семейству <tex> A </tex>. Если это не так, то мы можем перейти к рассмотрению дополнения семейства: к <tex> \overline{A} </tex>. К тому же, так как свойство <tex> A </tex> нетривиальное, то его дополнение содержит какой-то перечислимый язык. Пусть <tex> q </tex> {{---}} полуразрешитель какого-то фиксированного непустого языка из <tex> \overline{A} </tex>, то есть <tex> q \notin L_A </tex>. Тогда напишем такую программу:
<code>
p(x):
'''if''' p <tex> \in ~ L_A </tex>// можем так написать, потому что по предположению <tex> L_A </tex> {{---}} разрешимый '''return''' zq(x)
'''else'''
'''while''' ''true''
</code>
Если <tex> p </tex> не удовлетворяет свойству <tex> A </tex>, тогда будет выполняться всегда вторая ветка, и <tex> p \equiv \varnothing </tex>. Но пустой язык принадлежит <tex> A </tex>. Получили противоречие.
Если <tex> p </tex> удовлетворяет свойству <tex> A </tex>, то <tex> L(p) = L(q) </tex>, а <tex> q \notin A </tex>. Опять получили противоречие.
== Колмогоровская сложность ==
{{Определение
