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