313
правок
Изменения
Нет описания правки
}}
----
{{Утверждение
|statement=
Функция <tex>BB(n)</tex> не убывает.
----
'''Вывод:''' доказав предыдущее утверждение, мы проверили, что максимальное число шагов, которое может совершить программа и при этом остановиться, на самом деле растет с большей скоростью, чем любая вычислимая функция. Отсюда следует, что <tex>BB(n)</tex> невычислима.
{{Утверждение
|id=proposalU.
|statement=Функция [[Busy beaver]] невычислима.
|proof= По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы. Предположим, что функция [[Busy beaver]] вычислима. Тогда напишем такую программу
<code>
p():
'''for''' i = 1..BB(<tex>|\mathrm{getSrc()}|</tex>) + 1
do smth
</code>
Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(|p|) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.
}}
== См. также ==
