13
$\begingroup$

The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n>4$? What is so different about $n=4$ than $n=5$? Or $n=6$? Somewhere along the way there must be some fundamental difference, otherwise $S(n)$ would be, in principle, computable for all $n$, so what exactly is this difference?

$\endgroup$
6
$\begingroup$

The reason that no program can compute $S(n)$ is that if you knew what $S(n)$ is you could decide the halting problem - you'd know when to stop waiting. On the other hand, for each $m$ there is a program that computes $S(n)$ for all $n \leq m$ - it just uses a table.

If it were possible to prove the value of $S(n)$ for all $n$ (that is, for all $n$ we could prove $S(n) = \alpha$ for some $\alpha$) then we could compute $S(n)$ by searching through all proofs (this assumes that our proof system is valid). So for each proof system there is a minimal value of $n$ for which you cannot prove that $S(n) = \alpha$ for any $\alpha$.

Finally, the reason that we know $S(4)$ is probably because $4$ is a really small number. The number $5$ is slightly bigger, and so things get more complicated. There's no deep reason why we know $S(4)$ but not $S(5)$, just like there is no deep reason why we know the Ramsey number $R(4)$ but not $R(5)$ (though Ramsey numbers are of course computable).

$\endgroup$
  • $\begingroup$ Thanks. The middle paragraph was essentially what I was wondering about (and it's a proof of Godel, correct?). So it actually could be that $S(4)$ has a proof in our formal system but $S(5)$ does not. $\endgroup$ – PeteyPabPro May 29 '13 at 1:11
  • $\begingroup$ Presumably. If $S(n)=\text{"}S(n)\text{"}$ is unprovable but true that $S(n)\neq\text{"}S(n)\text{"}$ is also unprovable, and so we have a statement which can be neither proved not refuted. $\endgroup$ – Yuval Filmus May 29 '13 at 4:18
  • $\begingroup$ You still haven't really explained why we can be so sure S(4) is correct, whilst S(5) or higher we can never know. Is it because we're not 100% about S(4), but only "very almost" sure? $\endgroup$ – Dan W Apr 24 '15 at 0:55
  • $\begingroup$ We are 100% sure about S(4). I don't think there is any deep reason behind our ignorance regarding S(5). It's just the current limit of our knowledge. $\endgroup$ – Yuval Filmus Apr 24 '15 at 0:58
  • $\begingroup$ I believe there is a really strong proof system and a 6 state 2 colour turing machine such that it can be proven that there's no proof in that system that it will never halt and it will not halt before any algorithm that can be proven in that system within a googol characters to eventually halt halts. $\endgroup$ – Timothy Aug 14 '18 at 3:00
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Could you quote relevant part? $\endgroup$ – Evil Nov 11 '17 at 21:06
2
$\begingroup$

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, which (similar to technological advance) is a continually advancing frontier based on mathematical & computer science research.

[1] Busy beaver problem, a new millenium attack, van Heuveln et al

[2] Small Turing machines and generalized busy beaver competition, Michel

[3] On running time of the shortest problems, Batfai

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.