Вычисление функции занятого бобра

Функция максимального сдвига занятого бобра имеет известные значения для n ≤ 4 . Есть ли какая-то основная, структурная причина, по которой немыслимо, что мы когда-нибудь найдем S ( n ) для n > 4 ? Что такого отличного в n = 4 от n = 5 ? Или n = 6 ? Где-то на этом пути должна быть какая-то принципиальная разница, иначе S ( n ) будет, в принципе, вычислим для всех n , так что именно$S(n)$$n\leq4$$S(n)$$n>4$$n=4$$n=5$$n=6$$S(n)$$n$есть эта разница?

Причина, по которой ни одна программа не может вычислить заключается в том, что если бы вы знали, что такое S ( n ) , вы могли бы решить проблему остановки - вы бы знали, когда прекратить ждать. С другой стороны, для каждого m существует программа, которая вычисляет S ( n ) для всех n ≤ m - она ​​просто использует таблицу.$S(n)$$S(n)$$m$$S(n)$$n \leq m$

Если бы можно было доказать значение для всех n (то есть для всех n мы могли бы доказать S ( n ) = α для некоторого α ), то мы могли бы вычислить S ( n ) , просматривая все доказательства ( это предполагает, что наша система доказательств действительна). Таким образом, для каждой системы доказательств существует минимальное значение n, для которого нельзя доказать, что S ( n ) = α для любого α .$S(n)$$n$$n$$S(n) = \alpha$$\alpha$$S(n)$$n$$S(n) = \alpha$$\alpha$

Наконец, причина того, что мы знаем , вероятно, потому что 4 - действительно небольшое число. Число 5 немного больше, и поэтому все становится сложнее. Нет никакой глубокой причины, по которой мы знаем S ( 4 ), но не S ( 5 ) , точно так же, как нет никакой глубокой причины, по которой мы знаем число Рэмси R ( 4 ), но не R ( 5 ) (хотя числа Рэмси, конечно, вычислимы) ,$S(4)$$4$$5$$S(4)$$S(5)$$R(4)$$R(5)$

Scott Aaronson discusses this here. He and his co-author find an explicit upper bound on $n$ for which $S(n)$ can be computed.

another angle, with an informal sketch of an answer, which would take a long time to technically flesh out with further research (ie it is basically a research program): there is some preliminary evidence that the limit of what is computable about the Busy Beaver function is a measure of algorithm complexity, with two refs below that hint at this direction.[1][2] roughly, small TMs with very few states cannot accomplish "as much" or "as sophisticated behavior" as more complex algorithms with more states. therefore calculation of it appears also to have a deep link with Kolmogorov complexity.[3] another way of looking at this is that what is known/computable about the Busy Beaver function also closely coincides with state-of-the-art in automated theorem proving, что (подобно технологическому прогрессу) является постоянно развивающейся границей, основанной на математических и компьютерных исследованиях.

[1] проблема занятого бобра, новая атака тысячелетия , ван Хейвельн и др.

[2] Маленькие машины Тьюринга и соревнования по бобровому труду , Мишель

[3] На время выполнения самых коротких задач , Batfai