3622
правки
Изменения
набросок теоремы Успенского-Райса
}}
== Теорема Успенского-Райса ==
<tex> A </tex> {{---}} разрешимое семейство языков.
<tex> L_A </tex> {{---}} язык свойства языков. Допустим, что он разрешим. Тогда напишем такую программу
<code>
p(x):
'''if''' p <tex> \in ~ L_A </tex>
'''return''' z(x)
'''else'''
'''while''' ''true''
</code>
== Колмогоровская сложность ==
{{Определение
p(<tex>\varepsilon</tex>):
'''foreach''' x <tex>\in ~ \Sigma^* </tex> // перебираем слова по возрастанию длины
'''if''' <tex> K(x) > |p|</tex>// теорема о рекурсии используется здесь
print(x)
exit
