1679
правок
Изменения
→Busy beaver
|id=proposalU.
|statement=Функция [[Busy beaver]] невычислима.
|proof= Предположим, что это не так. Тогда напишем такую программу
<code>
p():
Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(p) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.
}}
== Аналог I теоремы Гёделя о неполноте ==
{{Теорема
