How the Slowest Computer Programs Illuminate Math’s Fundamental Limits

&gt; The busy beaver game is all about the behavior of Turing machines<p>A busy beaver for lambda calculus is even easier to define:<p>the maximum normal form size of any closed lambda term of size n (or 0 if none exists).<p>The series [1] starts as 0, 0, 0, 4, 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 30, 42, 52, 44, 58, 223, 160, 267, 298, 1812, 327686, 38127987424941,<p>578960446186580977117854925043439539266349923328202820197287920039565648199686<p>Results are more fine grained than for TMs because these sizes are in units of bits (lambda and application measuring as 2 bits, and a variable bound by n&#x27;th enclosing lambda as n+1 bits).<p>Graham&#x27;s number is surpassed within 114 bits, while the smallest known TM for surpassing it takes 225 bits to describe.<p>[1] <a href="https:&#x2F;&#x2F;oeis.org&#x2F;A333479" rel="nofollow">https:&#x2F;&#x2F;oeis.org&#x2F;A333479</a>

One fascinating thing about the function BB(n) is that it grows faster than any computable function.<p>The proof of this is simple: if you had a computable function f(n), and f(n) &gt;= BB(n) for all values of n, you could use that to solve the halting problem, which in itself is impossible.<p>I used to implicitly assume that we can make concrete, closed-form, functions that grow as fast as we want them to. The above shows that this is clearly false.

&gt; Nevertheless, that incomprehensibly huge number is still an exact figure whose magnitude, according to Aaronson, represents “a statement about our current knowledge” of number theory.<p>This is, of course, contradicted later in the article in which they point out that `BB(800)` (or so) has been proved independent of ZFC; there&#x27;s no really good reason to believe `BB(27)` is not likewise independent. There may still be a truth of the matter about the value of `BB(800)` or `BB(27)` (as the case may be), since ZFC hardly encompasses all truth, but calling such a number an &quot;exact figure&quot; is a bit like claiming to know the birth date of Julius Caesar down to the millisecond: Implausible to start with, and the closer you look the more you wonder, &quot;what does the question even <i>mean</i>? Relative to what standard?&quot; (In the one case, &quot;of time&quot;; in the other, &quot;of mathematical truth&quot;.)

I created the visualization for this story by running BB(5). You can find the source code (a full Turing Machine implementation that runs BB) and visualizations of other BBs in my blog post <a href="https:&#x2F;&#x2F;catonmat.net&#x2F;busy-beaver" rel="nofollow">https:&#x2F;&#x2F;catonmat.net&#x2F;busy-beaver</a>.

&gt; If you knew all the busy beaver numbers, then you could settle all of those questions.<p>A lot of important questions in number theory could be answered, but not all. For example, the mentioned Collatz conjecture (3n+1) is of different type. To prove this conjecture you need to prove the halting for EVERY argument. Checking halting of a single program will not be enough, so busy beaver won&#x27;t help. This is a next level task in the Arithmetical Hierarchy [1]. Though, in fact, you can define the next level Busy Beaver that could solve Collatz conjecture. To solve more complicated problems you need high-order Busy Beavers.<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Arithmetical_hierarchy" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Arithmetical_hierarchy</a>

Very interesting. In the past, I spend some time on finding the largest number that could be calculated by a Brainfuck program when the memory cells can hold arbitrary large numbers (and not be restricted to bytes as with the official language). It takes a bit longer to take-off. For my findings, see: <a href="https:&#x2F;&#x2F;www.iwriteiam.nl&#x2F;Ha_bf_numb.html" rel="nofollow">https:&#x2F;&#x2F;www.iwriteiam.nl&#x2F;Ha_bf_numb.html</a>

I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?

Andrej Bauer: Is it just me, or is the busy-beaver function a figment of classical mathematics?<p><a href="https:&#x2F;&#x2F;twitter.com&#x2F;andrejbauer&#x2F;status&#x2F;1327670607824252928" rel="nofollow">https:&#x2F;&#x2F;twitter.com&#x2F;andrejbauer&#x2F;status&#x2F;1327670607824252928</a>

&gt; 6,561 possible machines with two rules<p>Huh? How do they get to that number? A TM state can be described with 4+2log2(N) bits, where N is the number of states, so a 2-state TM can be specified with 12 bits, so there are at most 4096 of them. Where do the extra 2465 come from?

After reading this kind of fascinating stuff, I feel ashamed that I am wasting the opportunity of having a human mind by writing CRUD applications (though I am nowhere near as smart as this stuff requires one to be - I can barely clear whiteboard coding interviews).

I too have read Scott Aaronson&#x27;s blog.