313
правок
Изменения
→Альтернативное доказательство с использованием теоремы о рекурсии
Допустим, что <tex> K </tex> вычислима, тогда напишем такую программу:
<code>
'''foreach''' x <tex>\in ~ \Sigma^* </tex> // перебираем слова по возрастанию длины
'''if''' <tex> K(x) > |p|</tex> // теорема о рекурсии используется здесь
'''print'''(x) '''exit '''
</code>
