3622
правки
Изменения
м
Начиная с Длина этой программы меньше длины минимальной программы, которая возвращает <tex> x_0 x</tex>, на пустом входе. Поэтому возникает противоречие. Следовательно <tex> f(x) > |p| K </tex>невычислима.
→Альтернативное доказательство с использованием теоремы о рекурсии
====Альтернативное доказательство с использованием теоремы о рекурсии====
Функция <tex> K(x) </tex> равна минимальной длине {{---}} это минимальная длина программы <tex> p : p(\varepsilon) = x </tex>.
Допустим, что <tex> K </tex> вычислима, тогда напишем такую программу:
<code>
'''foreach''' <tex>x\in ~ \Sigma^* </tex> <span style="color:Green">//перебираем слова по возрастанию длины</span>
'''if''' <tex> K(x) > |p|</tex> <span style="color:Green">//теорема о рекурсии используется здесь</span>
'''printreturn'''<tex>(x) '''exit''' </tex>
</code>
==Применение==
