# The Boundary of Computation ## Метаданные - **Канал:** Mutual Information - **YouTube:** https://www.youtube.com/watch?v=kmAc1nDizu0 ## Содержание ### [0:00](https://www.youtube.com/watch?v=kmAc1nDizu0) Segment 1 (00:00 - 05:00) I recently rewatched the number file videos on ridiculously huge numbers like Graham's number and tree three just complete brain melting monsters but this time one part caught my attention is busy beaver of a Google bigger than tree of a Google yeah I think the answer is yes it's that kind of ballpark you know yeah oh yeah that's certainly these are monsters these are monsters and so I went down the rabbit hole of the Busy Beaver numbers and oh my God I'm convinced this is the most mind-blowing function in existence I found out that no algorithm even in theory could produce numbers that keep Pace with this beast and if there was some magic Brute Force computation of even some small values then that would involve resolving centuries-old unsolved problems in mathematics and some mathematical systems lose the ability to prove its values Beyond a point I mean what this thing which is just a fixed sequence of numbers is quite literally a boundary separating the computable from the uncomputable you'll see what I mean now I have to admit I'm a bit out of my depth here all I've done really is read the work of Scott Aronson and a few others so consider this just a forwarding of those ideas and an introduction into the crazy worlds of the Busy Beavers first thing we need a binary turing machine this is an abstract device that acts on an infinitely long tape made up of ones and zeros the machine has an internal State the machine then reads a cell and then depending on its state and when it reads it writes either a one or a zero then it shifts either left or right and transitions to a new state also it may halt completing the computation not to represent all of the machine's Behavior we use a state table where we have the machine State along the top and the value it reads along the left side also there is a special halt State because there are four states not counting the halt State we say this is a four-state machine now for every combination of the state and the value it reads we have three actions to determine the value to write how to shift and what state to transition into for example if the machine is in state a and reads a value of zero then we would look here to determine the actions in this case we would write a value of 1 shift leftward and change the state to D so if we start with an all zero tape and in state a then this machine operates like this now there are a few things we need to know about Alan turing's invention first the church tearing thesis suggests any computation that is any finite sequence of steps applied to some input to produce some output is equivalent to the operations of some turing machine that's a bit of an oversimplification but it's good enough for our purposes this means all of computation all algorithms may be thought of as Turing machines and if we make statements about Turing machines we can say those apply to all programs any python function C plus program literally anything your computer is doing and second Turing proved no algorithm exists that receives as input any state table and any input tape and decides whether the machine will halt on the tape such a problem is undecidable this means there's no General way to shortcut computation to know if it halts you sometimes have to run it and wait and you might be stuck waiting forever never knowing the answer One Thing Worth emphasizing is this says there is no single algorithm that works on all machines and tapes with some specific machines and tapes A specialized algorithm might be able to decide if it halts and now we can ask what is the Busy Beaver function which will write a sigma n first we consider all end-state Turing machines so think of all possible State tables second we run each machine on a tape of all zeros next we look at all machines that halted the nth Busy Beaver Number Sigma n is the maximum count of ones written so each machine that halted will have written some number of ones over the all zeros tape Sigma n is the max number of ones written by some machine the machine that achieves this Max is called The Busy Beaver machine Let's do an example let's say n equals two so we have a two State table to consider I'll start by just making up the machine's actions now to see what the machine does we'll show the tape after each operation we start with all zeros and then after a right shift and state transition we have the next tape and this continues as we can see we've written two ones but could we have written more yes it turns out if we used this turing machine we would have gotten ### [5:00](https://www.youtube.com/watch?v=kmAc1nDizu0&t=300s) Segment 2 (05:00 - 10:00) this tape history which produced four once and this turns out to be the most possible so Sigma 2 is 4. because this machine achieved the max amount of ones it's a busy beaver machine and we continue this process the Busy Beaver for three states gives this tape history which ends with six ones so Sigma three is six and for four states we have this busy beaver State table and that produces this tape history ending with 13 ones so Sigma 4 is 13. and 5 States well Humanity has not yet been able to calculate this number to see what's happening let's ask how many end State term machines are there this many we see that the number of machines grow exponentially within so for the number of states we've considered so far that's a lot of machines to handle when we had four states that involved over 25 billion Turing machines and us smart humans determine definitely that the most number of ones they could print is 13. and that was hard work the difficulty is in determining which machines will halt there's no General solution so individual machines need to be theorized over for years Whittle down to a small group that Halt and ran to produce the max count of ones and we haven't been able to calculate it for five states since that involves trillions of machines each more complicated than before and this struggle barely reflects how truly Untouchable this function is let's start with the fact that Sigma n is not even a computable function is one which involves a finite sequence of steps to produce the output from the input and we don't have that because some machines will run forever and that whole time we'll think that one might be a busy beaver so there's no finite computation we can do these are not computable so you may ask how can we compute these for any numbers like Sigma 4 well that's a subtlety the non-computability comes from the lack of a finite procedure for all n but for a specific n which brings a finite set of machines we might be able to analyze our way to the answer okay it has been shown that this sequence grows faster than any computable function I'll say that slower out of all possible functions which receive an integer n and use any algorithm to return an integer in finite time the Busy Beaver function Beyond some value of n will grow faster than it that's expressed like this is absurd the ridiculously general practice of merely taking steps that is of processing an input in any conceivable way is damned to lose to this Godly series to really get this let's take a shot at the king I'm going to construct a challenger my own fast growing function I'll start by inventing some notation let's say a question mark means an exponential version of a factorial so for question mark is 4 to the 3 to the 2 to the one and we evaluate from the top right downward giving us about 262 thousand a pretty big number from four now let's consider four question mark we know four question mark is about two hundred sixty two thousand and now we're reapplying the question mark giving us a massive Tower of exponentials 262 000 terms tall and remember we evaluate exponents from the top down so two question marks in and we're already at a useless number next I'll Define the dash question mark it's defined as if we apply it to four then that's four with many question marks how many we will have four question mark question marks you remember how ridiculously out of hand things got with only two question marks well now we're going to do that many more times in fact about 262 000 times so this is bananas and let's push it for Double Dash question mark is defined similarly except using Dash question marks this time to be clear we evaluate this expression from the left so we start with four dash question mark which is that ridiculous number I just described then we take that number and feed it back into the dash question mark giving us something Beyond Comprehension and we do that many times in fact we do that an unspeakable number of times so this is utter insanity and now my sequence my attempt to Dethrone The Busy Beavers is this so how well does this thing keep up with the Busy Beaver function it's not even close sure for small n my function is larger but beyond a cernan The Busy Beavers are totally out of sight in fact at which end does the Busy Beaver sequence surpass my sequence well we can use some bounds on gram sequence which is a much faster growing function than mine to relate gram and sigma we know this and this which are probably very ### [10:00](https://www.youtube.com/watch?v=kmAc1nDizu0&t=600s) Segment 3 (10:00 - 13:00) loose bounds this makes me guess Sigma overtakes my function probably around 10. just a guess I wouldn't be surprised if it's eight the point is we are barely off the kitty slope and Busy Beaver wrecks my function and here's the crazy thing the reason we know Busy Beaver overtakes my function is because my description of the function Ends by merely specifying a finite procedure of how to produce the output from the input The Busy Beavers had me beat my sequence was computable so I'm finished and it wasn't even a fight and now things start to get really weird and Abstract it starts with the fact that there exists a 27 State turing machine that halts if and only if gold box conjecture is false one of the oldest most famous unsolved problems in mathematics it states that every even integer greater than two is the sum of two primes and no one in history has been able to prove it what this means is if Sigma of 27 was computed the direct way involving deciding which machines Halt and which don't then that would involve resolving gold box conjecture since we would have declared whether the goldbach machine halted if it halted the conjecture is false otherwise it's true and something is similarly true for the Riemann hypothesis as well now to be exact there might be some weird paths to calculating the Busy Beavers without actually answering these open problems but that's besides the point is these numbers contain information about a massive portion of all of mathematics and it actually gets stranger it turns out there are true statements like say Sigma of a thousand equals some number K that cannot be proven in our normal axiomatic systems of mathematics this is to say Beyond a point math loses the ability to make claims about these numbers which is just Why what now to arrive at this we'd have to discuss a good number of other Concepts so I'll save that for a follow-up video to end I'd like to point to the Busy Beaver World Scott Aronson's blog and papers are a great place to start he understands this really well and points to a lot of other work like efforts to prove bounds related to Graham's number or bounds on bb6 or bb7 in general there's glory to be had in constructing massively productive machines with as few States as possible so people are working on it and the real implications for the world of algorithms and the foundations of mathematics so go check it out if you're as interested as I was also I gotta say thank you to my patrons it's great to see people supporting me for this weird type of technical content so thank you to them and everyone else as well until next time the one issue I have with the Busy Beavers is the name is dumb sounds like a kids show like what are we doing --- *Источник: https://ekstraktznaniy.ru/video/38930*