Hi!

Over the past few months, I have read countless blog posts that have sparked a fascination on new topics. One of the coolest blog posts I have read, and one of the main inspirations for creating this, was written by Jeremy Kun and it covers the busy beaver (BB) sequence (link to his blogpost, you should read it). Very briefly, BB is a sequence of the maximun number of transitions any $n$-state Turing Machine (TM) can make assuming it does not loop forever. Traditionally, and for my brief description, BB assumes a binary alphabet. Initially conceptualized in 1961 by Hungarian Mathematician Tibor Radó, the sequence grows incomprehensibly fast. It is largely considered incomputable, as solving it would also solve the halting problem, which we know is undecidable. Only the first five values of BB have been formally proven, and only recently, in July 2024, the 5th value was determined to be 47,176,870. This means that there can be a maximum of 47 million state transitions in a 5-state TM if the TM is to halt. To prove this, every 5-state TM had to have been enumerated, and every TM was run on every possible string of at most size 5.

To illustrate how fast BB grows the following sequence shows the first five elements starting at $n=1$, along with what the floor of the 6th value is believed to be:

$$\begin{align*} \{1, 6, 21, 107, 47176870, 10 \uparrow \uparrow 15, ...\} \end{align*}$$

The 6th element, $10 \uparrow \uparrow 15$, is the repeated exponentiation of 10 fifteen times, in other words, $10^{10^{10^{.^{.^{10}}}}}$ (for reference, $10 \uparrow \uparrow 3$, or $10^{10^{10}}$, is equal to $10^{10,000,000,000}$ which is staggeringly larger than the meager $10^{80}$ atoms in our observable universe. I hope you can imagine how incomprehensible $10 \uparrow \uparrow 15$ really is). It represents the floor of the 6th value, but its true value has yet to be formally proved. To put the sheer size of BB into perspective, some modern-day C programs can contain thousands or millions of states, can you imagine the value of BB(1000)? More about BB can be read here.

I stumbled upon Jeremy's blog while trying to figure out what the hell the busy beaver sequence was since one of my questions in a Theory of Computation problem-set asked us to provide a reduction from $A_{TM}$ to prove a variation of busy beaver was incomputable. His post, while helping me understand what the sequence was, sparked an interest in me for a deeper understanding of computation, and its limitations.

The purpose of my blog is to document things I find interesting. I hope with this I can spark an interest in someone else similarly to how Jeremy was able to spark one in me with his blog post on busy beavers. I will be writing about things I may find interesting from class, and stuff I do outside of class.

I do not have much experience with developing complex web applications, and this was my first time in a while building a website. I wanted to keep it simple so I can focus more on what I write about and the projects I am working on this summer. I am using eleventy for static site generation, and a few plugins for codeblocks and $\LaTeX$. I strongly suggest if you are reading this and need to take any math courses, learn how to use latex to type homeworks - it makes everything so much better.