Way Bigger Than Graham's Number (Goodstein Sequence) - Numberphile

[@numberphile]

See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor)

[@TheDuckofDoom.]

This video is missing the basic point of the Goodstein sequence, and the rules it follows. He may as well be writing out arbitrary numerical expressions and claiming it does… something?

[@MijinLaw]

I enjoyed that. Honestly from the title and thumbnail I thought it was going to be something trivial like just adding more up arrows, but was actually very enlightening

[@Bibibosh]

hey numberphile, why does the fanuc computer cnc run so slow? the No1. software is fanuc. i use a brandnew fanuc machine. it lags.. also many functions arnt available which should exist. its an intesting topic. I have a video's worth of content... about trash talking Fanuc CNC Puma

[@paulthompson9668]

What is the smallest starting point for which the length of the sequence is greater than Tree(3)?

[@Bibibosh]

@ 42?

[@MichaelKah4712]

Wait, this got EVEN MORE interesting right when it stopped! We need a video about the speed limit!

[@robcoh]

I can't derive 55!

[@hans_bier]

Absolutely!

[@MrPlasterbrick]

Seconded

[@koenbres]

It was briefly mentioned in the Tree(g(64)) vs g(Tree(64)) video with Tony I think.

[@robertschreur5138]

Agree

[@AlexanderEVtrainer]

Definitely need to hear more about that arithmetic speed limit. It's hard to imagine why a finite operation (even a stupidly big one) would increase too fast for basic math laws to keep up with.

[@alexritchie4586]

I guess there's a couple of reasons. Firstly that the universe puts a hard limit on how fast information can be transferred, so if the number was so enormous that relaying the amount of information contained within it would exceed the predicted lifetime of the universe, actually calculating it before the end of all existence would have to exceed the information speed limit. Secondly, Landauer's Principle states that computation has a maximum efficiency in proportion to the temperature at which those computations are performed, so it may be the case that the number could never be calculated by any computer we can currently imagine that would operate at a temperature higher than absolute zero.

[@jerrr-c-squared]

@@alexritchie4586 I don't think that's what this is referring to, pure math couldn't care less about the physical limits of reality.

[@convindix]

@jerr-c-squared True, and another thing is there's nothing special about Peano arithmetic. There's are a ton of formal systems used in foundations of mathematics (PA, KP, ZFC, RCA_0, ATR_0, etc.), each with their own speed limits, some slower than Peano's, some faster. There wouldn't be any reason for Peano arithmetic to be the special one with connections to the physical universe

[@Rubrickety]

@@alexritchie4586These things are true, but aren’t part of the unprovability results, which hold even if the universe lives arbitrarily long. They’re related to topics like primitive-recursive functions. I agree a video on this would be interesting. It’s a challenging topic though.

[@levipoon5684]

​@@alexritchie4586 I'm not an expert, but I believe this has more to do with a logical limitation than any physical one. The proof of Goodstein's theorem goes like this: We can define the notion of ordinals, which allows us to essentially count past infinity. The ordinals start with the familiar 1, 2, 3, ... And after all the natural numbers, we get ω, ω+1, ω+2, ... where ω is the first infinite ordinal. It turns out we can add, multiply and takes exponentials of ordinals in a coherent manner. Now start with some positive and for every number in the Goodstein sequence, replace all the base with ω. We can show that this sequence is strictly decreasing. Up till now, I believe everything still works in Peano arithmetic. Now we invoke a property of ordinals: there is no infinite strictly decreasing sequence of ordinals (this is what he means when he said all the blocks will eventually be broken down) and we conclude that the sequence must eventually reach 0. This fact is not provable in Peano arithmetic. I think this is related to how Peano arithmetic is limited in how far its proof can reach in the so-called fast-growing hierarchy, which is precisely indexed by these infinite ordinals, and how the length of the Goodstein's sequence as a function of the initial number is out of reach on this hierarchy. I don't really know the details though.

[@josephoduor2358]

I was jokingly telling myself 4 would probably take like 6 million steps thinking that was a wild exaggeration, only for him to write down 10^10^8.

[@error_6o6]

Well, it was a wild exaggeration. A wild underexaggeration.

[@EaglePicking]

Brady's "10 or 12", compared to your "probably like 6 million", were both about equally wrong if we're comparing them to the correct answer ;-)

[@userchrh]

6 million… that reminds me of something…

[@anand.suralkar]

Jews?

[@JohnSmith-nx7zj]

8:02 per Wikipedia the length of the sequence for 19 is basically f(w^w) applied to 8. That is indeed way beyond Graham’s number.

[@venisontron]

I love when numberphile gets into this really heady place where math and philosophy start to bump against each other. Goodstein proves something, and then decades later someone else proves that you can't prove it, but it's still true? That's the content I come here for.

[@isaacwebb7918]

They proved that it can't be proven within the axiomatic system that people usually use to prove stuff about finite numbers. Basically, we have a system (or lots of variations on systems, but Peano is one of the standards) for doing math with numbers, and it works really well, but Godel proved that no system like that could prove everything that was true. So, the question: what's a statement that is true but can't be proven by the system? A hard question, of course: to show that your suggestion qualifies, you have to know it's true, but how can you know it's true and also show that our systems of proof can't do it? This works because Goodstein proved it by using a bunch of math we usually don't use except when we're working with infinities, and then later they proved for sure that no finite axiomatic system could prove it. So we know it's true, and we know that you can't solve it within the axiom system, so we have a true statement about finite numbers that the finite-number system can't prove.

[@NeinStein]

You gotta love this stuff! 1: 1 2: 2 3: Bigger than can be calculated within our finite universe

[@anand.suralkar]

3:6 4:10^10^8

[@carlbenjaminjr7087]

It's actually quite simple to calculate once you figure out the pattern, just very monotonous. Every "block" in the form n^2-1 takes n*2^n -k steps to complete, where k is the beginning value of n when the sequence first reaches the state n^2+n^2+...+n^2-1 Eg. 4 (2^2) turns into 3^3-1 or 3^2+3^2+3^2-1 It takes 3*2^3-3 (21) steps to reach the state 23^2+23^2+0 The next step is 24^2+24^2-1, and the pattern repeats 24^2-1 takes 24*2^24 -3 (402,653,181) steps to reach the next significant block (402,653,183+0), followed by 402,653,184-1 This is the "final stretch", and it will take 402,653,184*2^402,653,184 -3 steps from this point until the sequence to finally reaches 0, which is indeed greater than 10^10^8

[@NoriMori1992]

Reminds me of TREE(3).

[@isaacwebb7918]

@@NoriMori1992 Gotta love a sequence that goes from single digits to universe-crushingly large in no time flat. The Goodstein sequence at least has a couple intermediately-big entries that can be put neatly into power towers, and doesn't pass Graham's number until f(12). The TREE(n) series goes straight from TREE(2)=3 to TREE(3) being bigger by far than anything discussed in this video. Then the SCG() series (by the same guy who did TREE()) goes even harder. SCG(0)=1, SCG(1)=3, SCG(2) has something like 20 digits, and SCG(3) is big. It's bigger than TREE(3), or TREE(TREE(3)) or TREE(TREE(TREE(TREE...TREE(3)))) nested TREE(3) layers deep.

[@BoscoBenson]

Like the TREE function.

[@Xnoob545]

If anyone's watched the extra videos about TREE vs. Graham and is familiar with fast-growing hierarchy, Goodstein sequences are approximately f_ε_0 (n) level (that's epsilon nought) Way way faster than Graham's omega + 1, but WAY WAY WAY slower than TREE (that one goes way beyond even Gamma_0)

[@alansmithee419]

That's a capital gamma btw, for the feffermann-schute ordinal. There's a lower case gamma_0 much much earlier in the hierarchy (depending on notation), which comes shortly after epsilon_0.

[@hillabwonS]

@@alansmithee419 whats the lowercase gamma ordinal?

[@rochellekesselring4865]

Thank you for the reminder of that scale and clarification.

[@alansmithee419]

@@hillabwonS And then long long after Γ_0 (like, it's not even funny) you get the privilege of meeting the *small* veblen ordinal XD. Which is finally on par with TREE(n) (so I've heard at least, IDK).

[@hillabwonS]

@@alansmithee419 WHATS THE LOWERCASE GAMMA ORDINAL

[@adb012]

How it takes "infinity" machinery to proof facts about finite numbers kind of reminds me of how it takes calculating negative square roots (and hence complex numbers) to find REAL roots in polynomials with REAL coefficients. The imaginary parts always magically cancel leaving you with a real number, but a real number that you could not access unless you take a detour through the complex world.

[@josenobi3022]

"a real number that you could not access unless you take a detour through the complex world" doesn’t mean anything

[@dlevi67]

@@josenobi3022 It doesn't mean anything unless you understand the process being described. Although 'access' is not perhaps the best word for it.

[@josenobi3022]

@@dlevi67 well if you understand it, explain it better then

[@adb012]

@@josenobi3022 ... It may not mean anything to you, but that's on you. There are some polynomials with REAL coefficients that you make them equal to zero and you cannot find a method to find all the REAL solutions (values of x that make the equality true) by staying in the REAL numbers. Coefficients are real. X is real. Everything is real. But to find X you MUST go to the complex world, and the complex world will automatically take you back to the real world by making the imaginary part equal to zero, thus finding the REAL values of X. That's what I meant, hence it does mean something.

[@dlevi67]

@@josenobi3022 The OP just explained it. BTW - before you object that you could calculate the solution with numerical methods, that is true, but you'd only ever calculate an approximation of it, not its precise value.

[@dentonyoung4314]

That was one of the best episodes yet. I had never heard of the Goodstein sequence until today.

[@numberphile]

Glad you enjoyed it.

[@vytah]

For a deeper dive into Goodstein sequences, there's a video from PBS Infinite Series: "How Infinity Explains the Finite" and bit more technical by Sheafification of G: "2Fast2Finite: Breaking the natural speed limit of finite numbers"

[@j0nasbs]

That escalated quickly

[@danielfaiz3386]

"wow why is it so big"

[@santiruga]

😂😂

[@harveyjones1]

🤣

[@error_6o6]

VERY quickly

[@NoriMori1992]

"That really got out of hand fast!"

[@miannekahkol9556]

I love when sequences start off looking normal and then zoom off to absurd numbers at even more absurd paces!

[@joebloggs3551]

Yeah its interesting how often that happens. Like: TREE(1) = 1, TREE(2) = 3, TREE(3) = insanity. SCG(0) = 6, SCG (1) = crazy SSCG(0) = 2, SSCG(1) = 5, SSCG(2) = very big BB(1-4) = small, BB(5) = not that big, BB(6) = crazy

[@organon69]

"He had to reach out of the sandbox for tools to which he shouldn't really have had access." - a really rather delightful phrase.

[@40watt53]

Something someting cosmic horror...

[@redstonekid2222]

Like using an industrial excavator to build a sandcastle.

[@heatshield]

Sometimes I feel like this channel is just what I did as a kid by entering nonsense on a calculator then hitting equals until the battery died or I got an “E”.

[@numberphile]

Many of our favourite people start out doing stuff like that.

[@sadas3190]

More accurately this is what legendary mathematicians did before calculators. What happens if I just kept trying to break stuff

[@anand.suralkar]

Yeah as a kid I found out 355/113 as better approximation than 22/7 for pie and man I thought I invented something crazy I was in 6th grade

[@error_6o6]

@@anand.suralkar how does one discover 355/113 in 6TH GRADE without even using any sources

[@Xnoob545]

The proof for goodstein sequences always dying off involves replacing the "base" numbers in the power towers with omegas (like the ordinal infinity), and using rules of ordinals to prove it

[@MasterHigure]

To be more concrete, doing this you get a strictly decreasing sequence of ordinals, which by well-orderedness must terminate. It takes a little work to describe this explicitly. Basically, there is for each n a function fn given by "express in heredetary base n, swap each n with an ω" (completely analogous to the way this sequence repeatedly swaps each n with n+1). Apply function fn to term number n-1 of the sequence (regardless of the starting point). If you don't "break a block" as they say, the -1 is just a -1, which is strictly decreasing. If we do break a block that's even more decreasing (left as an exercise to the reader).

[@byungyoonchoi3744]

There's a fun video about this exact proof by Sheafification of g. Worth a check if you don't mind some hilarious editing

[@NonFatMead]

@@MasterHigure I think I have an intuitive feel for why this 'breaking down' of towers leads to such a proof. Let's see how it goes. As you take any number, x, in hereditary base n, and do the conversion from it being a collection of towers of n's (and some number of 1s) into (n+1)'s, you are essentially boosting it into a (very) much larger number. But we've just come from the universe of hereditary base n, and now we're going to turn the 'boosted' number into a collection of shorter towers of (n+1)'s (and some 'rubble' of a chain of 1s) - all by taking a single -1 chunk out of that tower. Now n+1 representations of those towers will gradually break down each of them into smaller and smaller towers in order to attain the same overall total. If we don't do it this time, we just have to wait for further along. For example, we might meet the x as the number 16 in one of these sequences, somewhere quite a long way along the process. If it was met whilst in hereditary base 2, it's obvious that it's 2^2^2 - that's a tall enough tower. But every representation of it in a higher hereditary base will shuffle the singular tall tower into much shorter component towers. At some point, the hereditary base you're in will catch up with even the biggest of these and render it into 1s. At that point, it's just a case of waiting for the -1s to catch up - importantly the growth of 'boosting' can no longer occur to the same degree, and it will spiral back down again. So for any 'worst case' situation where you come into contact with an x in your process that's just a huge tower of your current hereditary base n, you'll move eventually from that hereditary base, to one where the -1 knocks it down into a combination of much shorter ones. The hereditary base keeps increasing, knocking more of these down until they're 1s (more rubble!) and the -1s applied at every step will eventually take them all out because there's no more 'building' taking place for the towers. To give it an analogy (ish) - we have a tower of stone blocks (integers) that can be constructed into a huge, n-dimensional 'tower' of n-dimensional rooms (of n-rooms of n-rooms etc). But the rules mean only perfect towers can be formed. And there's one janitor who's taking away rubble, one block at a time, while the tower continues to move into higher dimensions. But every time it moves into a higher dimension, it has to rearrange itself into perfect towers in that dimension, which means it can end up in a situation where the janitor has cleaned up the rubble and takes a stone block from the smallest tower. When it moves into the next dimension, that can make it turn into more separate towers, each with fewer nested rooms (and even if it doesn't happen here, it will eventually.) The janitor will clean up eventually when everything is rubble.

[@dastoex]

Oddly enough, I find I can quite easily grasp why this always dies off conceptually. From a systematic standpoint, if you start with a finite number of power towers with a finite number of levels each, along with a finite number of trailing 1s, and all you ever do is remove a trailing 1 if there is one, or else disassemble the shortest tower into a finite number of towers which are all shorter than the original one along with a finite number of trailing 1s, the end of the process is inevitable. You never add a level to any tower, only remove them. And though it may seem like you're fractally making ever more smaller towers, there is a finite limit to each set you create. From this standpoint, the base and the fact that it keeps growing really makes no difference to the outcome, only to the number of steps required. Another way of looking at it is that you're always making all the towers wider, but never higher - and then you occasionally remove a level and slowly chisel it down into tiny pieces (while the others keep getting wider). Takes a hecking long time, but not forever.

[@Xnoob545]

​@@dastoex sounds perfect to me

[@ffc1a28c7]

We covered in my logic class showing that the Ackermann function (essentially the same idea of extending exponentiation and tetration) is what we call not "primitive-recursive". This is essentially saying that in Peano arithmetic, we can't prove anything actionable about it.

[@lkruijsw]

If your logic is restricted for Sigma 1 expressions (so no 'For All') for the induction condition you can't proof that Ackermann is terminating. This is a simpler example of incompleteness than Goodstein. The input of an Ackermann function can also be written as a very simple ordinal, a x epsilon + b.

[@EebstertheGreat]

It's not primitive recursive, but it's trivially easy to see that it is always defined. In fact, you can prove it always terminates using a tiny fragment of PA. After all, by definition, at each step the pair (m,n) decreases in m or decreases in n while m is unchanged, so all you need is the well-ordering of ℕ.

[@andywhelan8608]

An underappreciated aspect of this video to is that Goodstein was English and published this work during WW2, the same month as the dday landings even. Interesting to think that even during such an all consuming war such mathematical work was still being done.

[@kylebroussard5952]

By a military age man nonetheless...

[@rochellekesselring4865]

You did it again Brady! Awesome job

[@stevestarcke]

There is something about impossibly huge numbers that captures the imagination. I feel small in front of the incalculable. But I feel huge for imagining it. Thank you for this marvelous episode.

[@DDranks]

I've followed this channel for years (a decade?) but this might have been the most interesting video thus far. As having education in computer science, this really hits the home base.

[@zaffyr]

This reminds me of the ant on a rubber band: If you stretch a rubber band at any speed you want, if an ant walks across it at a costant speed, it will eventually reach the other end, no matter how fast you stretch. This comes from the fact that the amount of length to go gets increased just as much as the ant's progress. In the goodstein sequence, the ant is represented by the -1 math is so interconnected; it's beautiful

[@christiandior8726]

what a beautiful mind you are!

[@mathematicalmusings]

Only works if you stretch at a constant rate. If the ant is going at 1m/s and has 1 metre to go, you can clearly always stretch the band in the next second so it has more than 1 metre to go in the next second so it will never reach the end.

[@maksymisaiev1828]

@@mathematicalmusings no, it will eventually. As long as distance behind ant will grow, it will reach the end. The ant analogy doesn't work on non stretchable band, where you just add distance, but on stretch band, distance behind the ant is growing in the relation to stretching speed.

[@rmsgrey]

@@maksymisaiev1828 If you take a 2m band, have the ant walk for 1m then pause while you stretch the band, and repeat that process, and you double the length of the band each time you stretch it, then, after the first step, the ant has covered 1m out of 2m and is halfway along the band with 1m in front of it, then you double the band's length, leaving 2m in front of the ant. Second step, the ant covers 1m, is 3/4 of the way along the band, has 1m in front of it, then you double the band's length, leaving 2m in front of it. Third step, the ant covers 1m, is 7/8 of the way along the band, has 1m in front of it, which doubles to 2m. And so on. The ant will never reach the end - the distance remaining will always be oscillating between 2m and 1m. When you switch to the continuous case, with a band starting at 2m length, an ant walking at 1m/s, and stretching accelerating so that the band always doubles in length every second, having the ant moving while the band is stretching will never get it as far in a given time spent walking as it would have if the stretching waited during that time, then happened while the ant waited for it to catch up, so, since the discrete ant never reaches the end, nor can the continuous ant in this case.

[@jareknowak8712]

+1

[@ryanlind5239]

5:00 "10 or 12." Me: "Noooo Brady, it's gonna be something insane, like a thousand..."

[@RosimInc7]

No no, probably even bigger, like 1050!

[@cyclobutene]

@@RosimInc7 too big

[@bernhardkrickl3567]

To paraphrase XKCD: What if we used more axioms?

[@convindix]

Goodstein's theorem is true but not provable in Peano arithmetic Kruskal's tree theorem is true but not provable in the stronger system called ATR_0 The Robertson-Seymour theorem is true but not provable in an even stronger system called Π^1_1-CA_0 A theorem called "Borel determinacy" is true but not provable in the even stronger system Zermelo set theory For more math like this (even including weaker systems than Peano arithmetic too), what these theorems are, and what these systems mean, Harvey Friedman's book has a nice long introduction chapter (250 pages!) with all this and more in it

[@MijinLaw]

@@convindix Exactly. The point (as I understand it) is that no matter what laws we add there will always be true statements that cannot be proven within that system of laws.

[@convindix]

@@MijinLaw This is true but with a caveat. It's true in practice since all the theories like Peano arithmetic, ATR_0, Π^1_1-CA_0, Zermelo set theory, etc. that are useful enough to be given names and used as a foundation for mathematics are effective: for each of those theories, there is an algorithm that will tell you whether or not a given statement is an axiom of that theory. If a theory's axioms can be listed out (like they are on the Wikipedia articles for Peano arithmetic or ZFC) them it's effective, since the algorithm is just a switch statement that tests if the given statement looks like any of the axioms in the list. From Gödel's second incompleteness theorem, any effective theory stronger than Peano arithmetic (that's consistent) will have some statement that it can't prove. But there's nothing stopping you from just taking the set of all true statements as your set of axioms. Nobody does math in this system though, since all proofs should be useless due to being one step long and circular. This theory isn't effective, since there is no algorithm to tell whether a given statement is true (and therefore whether it is an axiom of this system.) But this theory can prove all true statements by definition. So Gödel's second theorem needs to be restricted to effective theories.

[@alonsoviton8278]

@@convindix What's the name of Harvey's book?

[@error_6o6]

@@convindix”what if we used MORE axioms?”

[@QuantumHistorian]

Always fun to see the incompleteness theorem coming up. I knew of other examples, but none in strictly finite mathematics. Just really hammers home that what is "true" in mathematics depends entirely on the axioms you decide to work from, rather than some intrinsic thought-independent reality.

[@AFastidiousCuber]

It's funny you say that because Godel interpreted the incompleteness theorems as evidence in favor of platonism.

[@nelus7276]

Some axioms describe reality and some don't.

[@biblebot3947]

@@AFastidiousCuberwell not really Platonism but realism. He believed that certain axioms were natural but not that mathematical objects exist in any sense

[@AFastidiousCuber]

@@biblebot3947 Godel was a lifelong platonist. Read, for example, the 1951 Gibbs lecture. He believed that certain axioms were preferable not just because they were natural but that they were actually true.

[@valvesofvalvino]

This reminds me of the ant travelling around a circle that keeps growing. The circumference starts at 1m, once the ant has travelled 1cm, the circle grows by another 1m. It seems illogical at first but the ant eventually completes a full loop. By then the circle has become massive. The key point is that there is proportionately more and more of the loop behind the ant and this is a part of the circle that the ant doesn't need to travel any more.

[@redpepper74]

dang, once the ant has made its way around the circle once, the circle has a diameter of e^100 note that this only works if the circle grows proportionally to the ant's speed. if we suppose the ant travels at a constant speed of 1cm/s and the circle grows at a speed of t m/s, where t is the seconds elapsed, then the ant will never make it past pi/200 of the way round the circle.

[@error_6o6]

Actually, I think they made a video about this before, but probably a long while ago.

[@xyz.ijk.]

​@@error_6o6 ... yes, that's where they are getting the idea from.

[@error_6o6]

@@xyz.ijk. oh

[@lynxfl]

The TREE(g64)th element of the Meta Goodstein Sequence is still finite

[@jamestappin4741]

But is it bigger than Rayo's number?

[@taxicabnumber1729]

The TREE function grows much faster than the Goodstein Sequence, which grows much faster than the G function. So TREE(TREE(3)) >>> Goodman(TREE(G64)). TREE also has a big brother called SCG, which is based on graphs rather than trees and grows much faster than TREE (or any salad number composed of nested TREE functions, etc). And Rayo's number is much, much larger than any of those.

[@shophaune2298]

@@jamestappin4741 No. Because of order of operations here, MGS(TREE(G(64))) ~= TREE(G(64)). It only takes ~7300 rayo symbols to define BB(n), so BB(BB(2^65536)) >> TREE(G(64)) takes around 15000 symbols. Rayo's number is the largest number you can make with 10^100 symbols.

[@Einyen]

@@taxicabnumber1729 So GMS(12) > G(64) "GMS = Goodstein Meta-Sequence", what is the smallest x so that GMS(x) > TREE(3) ?

[@david-melekh-ysroel]

​@@Einyen it would be GMS(o(4)) Where o(4) is my friend's omicron function of 4, it's valued at 4^^4, in other words : 4 tetrated to 4

[@jimmyzhao2673]

The ending of this video was Brilliant !

[@WRSomsky]

To paraphrase D.Adams: It's big. Really big. You won't believe how vastly, hugely, mind-bogglingly big it is. I mean, you may thing Graham's Number is big, but that's just peanuts to this! Listen! 😁

[@NekuraCa]

Love the gyrobifastigium on the shelf in the background

[@error_6o6]

Just noticed that along with what I think is a rhomicuboctahedron on the top shelf and what I think is a icosadodecahedron.

[@TheTaxiDriver1729]

there is a great video about this topic by PBS Infinite Series called How Infinity Explains the Finite

[@murmol444]

yeah, I remembered a similar problem about cutting Hydra's heads and thought it was on Numberphile. But it was PBS for sure

[@RobinDSaunders]

Both channels have covered it: Numberphile's video is called "The Hydra Game", from April of this year.

[@SuperN57]

I never thought numberphile would cover this. I know what I'm watching for the next 17 minutes

[@bradleysampson8230]

Definitely need a sequel to this video! Loved it!

[@denelson83]

To quote Freya Holmér, a Goodstein sequence can "yeet off to fucking wherever" before coming back down to 0.

[@RibusPQR]

I want Tony Padilla to do a tier list of fast-growing sequences, and rank Goodstein's meta-sequence vs Tree.

[@ianstopher9111]

It is slower growing than Tree.

[@zaeny]

Richard Elwes is awesome. He taught me geometry at Uni of Leeds back in 2012 :)

[@KaedennYT]

I wouldn't mind a proper deep dive into Goodstein's own proof, including all of the fancy (and ugly!) ordinal analysis. Please do a video on infinite regress; it's such a satisfying idea!

[@karlwaugh30]

I swear I've seen it presented somewhere... it's a weird one but kinda makes sense. I think you can get a sense of it if you play with a few numbers yourself...

[@diribigal]

Wikipedia sketches the proof that the Goodstein sequences die (though not the proof that Peano Arithmetic can't prove that fact)

[@valentinziegler1649]

The proof for termination is simple once you understand ordinals. It can also be seen shy that specific proof cannot be formalized in PA: It requires that ε0 is well ordered. Genzen showed that PA is consistent, only using primitive recursive arithmetic and the fact that ordinals up to ε0 are well-ordered. Therefore, PA cannot know ghe latter, otherwise it would be able to prove its own consistency, which violates Gödel‘s second incompleteness theorem. Now the above Argument doesn’t exclude the possibility that there might be another proof in PA avoiding these ordinals. That is much more technical.

[@FranklinLee-t3k]

For the sequence starting with the number 4, the largest term in the sequence is 201326592^201326591 - 1, which ends in the digits 4457003007. And that is when you finally start subtracting 1 until you get to zero.

[@asheep7797]

I believe it first appears when it stays constant (where the expansion is b + (b - 1), and adding one to the base is counteracted by the subtraction (the b in (b - 1) is not increased.) When it becomes b, that’s when it starts to decrease.

[@FranklinLee-t3k]

@@asheep7797 True

[@pmcate2]

Are you saying that it strictly decreases from there?

[@FranklinLee-t3k]

@@pmcate2 Yes. Because since there are only 1s left, the base change doesn't affect anything.

[@wfcyellow]

No, the biggest number is 57. I think.

[@javen9693]

What about 56

[@abdulwasiq2056]

No, 42 it is.

[@not1not2but3]

Hmmm I come up with (4^3)-9=55….wait. Dang it. Thought I had it.

[@ThisIsAYoutubeAccountAsd]

I tested all integers from -(10^10) to 56 and your claim holds, so it's very likely that you're correct.

[@xinpingdonohoe3978]

Seriously? How can you possibly think that? That's ridiculous. Numbers like 24 exist. Did you just happen to forget about them?

[@caleblatreille8224]

This is very reminiscent of the video Tony Padilla does about Oresme, with the ant with the expanding rubber band. People seriously underestimate the power of that -1!!!!

[@alejrandom6592]

"Infinite number systems are not to be ignored Watson. They help us understand sequences, that grow too fast for the Peano Axioms to comprehend..." -Sherlock Holmes

[@aarona3144]

Good thing he's subtracting 1 each time. You wouldn't want these numbers getting to big!

[@Calmerism]

My mind was blown by the fact that minus one eventually beats some special kind of x to the x function 🤯

[@maksymisaiev1828]

that is for this case. And that is not that hard to see. As we see in case of starting 4, when we reach number 26, the outcome number is smaller than 3^3^3, and any next calculation by will for sure be less than sequence rule (for example, the next arithmetic representation will never be bigger than 4^4^4, 5^5^5 and so on). In short, the representation of sequence will always have some limit, which creates lower limit and than lower limit until you have just 1s. Same with 3n+1 series. It looks like multiplication by 3 should give big result over and over despite dividing by 2.

[@Calmerism]

I don't think hailstone numbers really compare to this, they are one linear function in a battle against another linear function. Goodstein sequence is a constant factor against an exponential function that is commonly known to grow crazy fast - and still the constant wins! (obviously layman here, if in doubt it's more likely than not that I am terribly wrong)

[@fwiffo]

Goodstein Sequence: "I get bigger than Graham's number really fast and can't be proven with Peano arithmetic!" Busy Beaver numbers: "Hold my beer."

[@convindix]

The funny thing is Peano arithmetic does prove that all the Busy Beaver numbers exist. There's a gap where computable functions faster than Goodstein aren't provably defined, but uncomputable functions like Busy Beaver are...

[@neoboletuserythropus3111]

Rayo's function: "That's cute"

[@fwiffo]

@@neoboletuserythropus3111 I'm not convinced that Rayo's function is in a significantly different class from a googleology terms. A value expressed in the language used in Rayo's function should be convertible to a Turing machine in at most a polynomial multiple of size. Also, it has the problem of lacking a precise enough definition. Busy Beaver numbers have a completely precise definition.

[@Peter-qz8qs]

I was reading about the incompleteness theorems, and Goodstein's theorem (that Goodstein sequences always go to 0) came up as an example of a truth not provable in Peano Arithmetic. Very interesting to me that you made a video about the sequences so recently!

[@hinumbercruncher]

Great video, really enjoyed it. From my limited knowledge I thought that Godel had shown that some propositions are undecidable , i.e. that the axioms could be used to show that the proposition is true, but also that the proposition is false. I wasn't aware that there are unprovable things, i.e. that may not be proven at all using the axioms. I also wasn't aware that you could prove something to be true outside the axioms. These are topics that deserve more videos!

[@germansnowman]

The slow but eventual dying of the sequences reminds me of the extremely slow “evaporation” of black holes via Hawking radiation.

[@Gamesaucer]

This reminds me of the hydra thing, where you keep adding copies of parts of the graph after removing a node. But that one always seemed kind of convoluted to me because of the complexity required to make it work (you can't just duplicate heads because that's never going to end). This is kind of the same thing, but it's a lot easier for me to grasp. It's just "increase each number that's not a 1 by 1". And then "cutting off a head" is just subtracting 1 from that total and rewriting it in the same base, immediately making it ready to do the growth step again. It feels a lot simpler, even though there's a similar amount of complexity going on behind the scenes.

[@JohnSmith-nx7zj]

It’s mathematically very similar and the two functions have ‘essentially’ the same growth rate. In a certain precise mathematical sense.

[@goncalofreitas2094]

The saga of big numbers continues 🔥

[@RobinDSaunders]

As others have said, please make a video explaining the relationship between fast-growing sequences and the limits to what given axioms can prove :) (mentioned right at the end, 14:30) It could clear up a lot of the confusion that shows up in comments whenever you discuss large numbers!

[@ukdavepianoman]

Never heard of Goldstein sequences before. Quite a "bizarre" thing to dream up. It's amazing how quickly they grow and yet they always collapse. From what I know about TREE(3) I assume TREE(3) is >> the number of steps for the Goldstein sequence for Graham's number - and where I've written much greater, it's probably much greater in a way that is incomprehensible.

[@shophaune2298]

You would be correct :)

[@JobvanderZwan]

The moment I saw that suppressed smirk at 5:00 I knew the real answer would be bonkers, hahaha

[@sebastiandierks7919]

I think there should be a follow-up video that explains - the limit of sequence growth to create incompleteness within the Peano axioms. - the proof that every Goodstein sequence goes to 0. What axioms were added to the Peano axioms in order to make that theorem provable?

[@richbuilds_com]

This man has a good way of explaining unexplainable things. :)

[@platinumpengwinmusic5564]

Fun fact! Context on the example number ³4 which comes to 1.3 x 10¹⁵⁰, the number of possible states of a 7x7 Rubik's cube is ~ 1.95 x 10¹⁶⁰.

[@liamdonegan9042]

I fail to see how those are related

[@vincehomoki1612]

@@liamdonegan9042 Probably just a comparison.

[@platinumpengwinmusic5564]

@@liamdonegan9042 I'm not the smartest guy in the world, but if you can't understand a simple number comparison for scale, then you probably can't understand the rest of this video.

[@liamdonegan9042]

@@platinumpengwinmusic5564 Language and math are different things though

[@empmachine]

How can you sit next to sooooo many unsolved puzzles??!?!? Flabbergasting !

[@orterves]

It's only necessary to do enough to prove they are solvable, the rest is left as an exercise for the viewer

[@empmachine]

@orterves you clearly don't know what you are talking about.. what nonsense!

[@orterves]

@@empmachine we're both joking right?

[@empmachine]

@@orterves hehehe yep 👍

[@quinn7894]

I like the Johnson solids in the background

[@rtpoe]

I like the 1x1x1 Rubik's Cube!

[@brouquier7172]

Great topic and great presenter! I hope we'll get to see more of Richard Elwes on Numberphile.

[@chaoticfishpond8607]

Thank you!

[@lkruijsw]

To proof that the Goodstein sequence finishes you have to use induction, but with the induction condition containing a generalization over a function. Peano Arithmetic can't generalize over functions.

[@tsjbb]

I liked this video and especially liked Richard's explanation :)

[@randomxnp]

There exists a finite number that is Tree(Goodstein sequence length(Graham's Number)).

[@EconAtheist]

and it's still precisely as close to zero as every other positive finite number, when compared to infinity. /not including 42 //which is a very special answer

[@peterhawes9680]

At 12:56 Woah! I was taught logic by Professor Jeff Paris at Manchester University! 😅

[@elistidham8494]

Been waiting for them to talk about this

[@charlievane]

14:09 but isn't the question about a potentially infinite sequence of operations, to be proved that it's actually finite?

[@CC-gg4oj]

Colour me impressed!

[@RandoBox]

What everyone is wondering is where this sequence is in the fast growing hierarchy?

[@alansmithee419]

f_{epsilon_0}(n), or thereabouts. I believe it's a bit (in googological terms - i.e. a lot) slower, but faster than any previous FGH function.

[@sarahspencer2359]

Epsilon 0 (w^^w)

[@codacoder]

Also very cool to hear axiom independence/provability mentioned! Meta-mathematics is underdocumented!

[@MultiplicativeDivision]

Reminded me of the Collatz Conjecture (not saying they are related)

[@FloydMaxwell]

3^^3^^3 gets "so big" because of the eval order. If it was 27^^3, that is 19,683. But it is 3^^27 (=7,625,597,484,987).

[@shophaune2298]

I think you mean to have single ^ arrows there. 3^^27 >>> 7.6trillion

[@FloydMaxwell]

@@shophaune2298 Apparently you are correct. Was just going from 40+ year old memories.

[@russelllomando8460]

so where am i wrong? 3^3^3 is base 3 ^9 multiply exponents = 19683

[@ludolfceulen]

Hyper-operations (tetration, pentation .... centation, googolation ....) are ALWAYS defined in this way (to give biggest result), nothing to discuss here.

[@henhouseharry6193]

​@@russelllomando8460 With tetration (power towers) you start at the top of the tower and work your way down. 3^^3 = 3^(3^3)=3^27

[@poppyseedsnuranium]

This's the kinda math that really gets my juices flowing. (I know that's weird.)

[@Wecoc1]

Might have to see a doctor about that one.

[@robcoh]

This puts you in a Ricci flow.

[@Jocedu06]

This is fascinating!!

[@xMepper_]

Rayo's will always be the biggest in my heart

[@TaneliPalonen]

Numberphile needs to make an app that allows people to donate computing power to universities.

[@redstonekid2222]

There's another notation, called FGHJ notation, which could display the sequence up to 6 (unsure about 7 given that it isn't shown). 4 is ee8, 5 is 9F4 (eeee9), and 6 is 1H9 (H = repeated G, G = repeated F, F is repeated e).

[@robertsobotka3725]

i'm simple, i see "bigger than Graham's number" - i click ✅️

[@lorenzo.bernacchioni]

I was waiting for this ❤

[@aramperez6476]

Brilliant video!

[@franklehman8677]

Surprised the proof via strictly descending infinite ordinals wasn't at least briefly sketched. It's fairly intuitive I think, once you get the swing of those omegas, how they can stand for simple integers. Notating using infinite ordinals also make the role of that "-1" much more obvious than a kind of handwavy description of gradually eating into blue blocks.

[@lkruijsw]

Then you first need to proper introduce the concept of ordinals.

[@valentinziegler1649]

At least he could have mentioned the concept.

[@scottdebrestian9875]

@@lkruijsw And before you can get to ordinals you need to talk about cardinals and then the Pope gets involved.

[@chaoticfishpond8607]

I did think about it. But it's a short video and the time it would have taken to introduce the relevant concepts would have derailed the story I wanted to tell about the non-provability of the theorem in Peano Arithmetic.

[@lkruijsw]

​@@scottdebrestian9875 You don't need to introduce cardinals before ordinals. You only need to understand well ordering.

[@Bill_W_Cipher]

Do we have a function that is the lower or upper bound to the length of any Goodstein sequence?

[@RobinDSaunders]

Yes, such a bound would be around level ε₀ of a fast-growing hierarchy (a self-contained explanation of these hierarchies would take a while, so you might like to Google them).

[@Alan-zf2tt]

I think the link between mathematical representation and events observable in nature is fantastic. Theoretical aspects that may or may not be related to events observable in nature are also fantastic. What I wonder and ponder is there any drift between theoretic and observable with unjustifiable implication of influence of one on the other.

[@6degreesN]

In a world where the numbers grow vast, Graham's number's a titan, unsurpassed. With Ryo's number in tow, They put on quite a show,

[@diggitus]

Points for the fun in leaving the fifth line to the reader's imagination, but you need to swap out "titan" for a one syllable word in line two or I'm calling the scansion police. :)

[@levimerrell-ov1nc]

I really hope there’s a follow up video on this! Very interesting topic

[@campbellsquires8096]

I love the 1x1 Rubik's cube on the wall

[@AgentM124]

Can we know the last 5 or 10 steps for numbers like 12 or 13 or more? Or can you only compute from the start?

[@jimmyh2137]

The last steps are always a sequence of 1+1+1+1... You'll have a single "big block" that gets converted.

[@AgentM124]

@jimmyh2137 I guess you're right and the length of that sequence is just... Long, before you get to the first power tower.

[@jimmyh2137]

​@@AgentM124 ​ you can break the tower relatively quickly, for example at 2:00 (the 19) you're breaking the 4^4^4 tower only three steps later. It would then be 8^8^8 -1 and you'll have to recalculate just like at 9:20

[@asheep7797]

Here you go! K - 10: 10 K - 9: 9 K - 8: 8 K - 7: 7 K - 6: 6 K - 5: 5 K - 4: 4 K - 3: 3 K - 2: 2 K - 1: 1 K: 0 (where K is the goodstein sequence’s length for n, where n is larger than three.)

[@JohnSmith-nx7zj]

@@AgentM124all the sequences terminate via this process: Eventually the -1s erode the structure until you get to 2x (where x is the current base). When you go to base x+1 you then get 2(x+1)-1 you then get (x+1)+1+1+……+1 with x 1s. At this point you keep increasing the base but subtracting 1 so the number actually stays the same for the next x steps. Then finally you have to break the last instance of the base. So at base (2x+1) you’re just left with 1+1+…..1 and then you just subtract 1 from the number 2x+1 times until you get to 0.

[@_Baleful]

0:54 - “The first step is two” Yes I can see that

[@Dysonsfear771]

The thing is that it eventually goed to a value dat is identical to the previous one. That enormous number then gets converted into ones. It takes the amount of steps equal to that number to go to 0. I'm more interested in how many steps it takes from start to the conversion into ones. This should be way way less

[@johnpearcey]

No matter how much maths you learn, there's always more that will blow your mind.

[@IrishEye]

-1 at the end of the universe, relaxing with the very last number of the Goodstein Sequence, "So how was it for you baby?"

[@rpow6861]

It's a bit like the ant walking along at 1cm per second on a piece of elastic that stretches at 1 mile per second. The ant would get to the end but it would take a very long time. Something like 10 to the 4000 power years

[@pinkraven4402]

TREE(N) finiteness is also unprovable with Peano axioms right?

[@AbbeyRoad69147]

No idea, but TREE(N) is provably more awesome, of course.

[@RobinDSaunders]

Yes, proving the finiteness of TREE(N) requires strictly stronger axioms than proving that Goodstein sequences terminate.

[@jlivewell]

Nothing better than an unproven theorem and a large number on a Tuesday! 😂

[@allanwrobel6607]

Another question, Is this not as similar example to trisection of the angle which was easily done but only with a marked ruler?

[@laurenceupton6379]

This is like the hydra numbers

[@rev1601]

But now I wonder: Back in the days you said about TREE(3) that it COULD in theory be proven to be finite by finite arithmetics only. The proof would need more symbols than what would fit into the universe (2 quad-arrow 10 if I remember correctly), but still, that qualifies as provable to me. Same for TREE(n) for all n, just with even more ridiculously long proofs. And now you're saying the Goodstein Meta sequence is completely unprovable in finite arithmetics? So does this mean it has to eventually outgrow TREE(n)?

[@valentinziegler1649]

For every specific value of n, Peano Arithmetic can prove that g(n) terminates. You can’t prove the general statement that for all n, g(n) terminates

[@shophaune2298]

TREE(n) might be provable in finitary arithmatics, but not necessarily using Peano's axioms - you'd need a stronger set of finitary axioms. For reference we know that Goodstein's Sequence grows around f_e0(n) in the Wainer fast growing hierarchy, while the weak tree(n) function grows faster than f_SVO(n), and the normal TREE(n) function grows notably faster still.

[@Xnoob545]

Sadly Goodstein does not outgrow TREE its pathetically small in comparison to TREE

[@rubenlarochelle1881]

5:50 If you're wondering why he says 10^(10^(10^(10^4))) is "longer than any of us would live to see" despite being just an adimensional number whose execution time is not specified, it's because the current age of the universe is "just" 8.1 * 10^60 Planck times. Even if each step would only one Planck time, the age of the universe would still be NOTHING next to it. Even if each and every single atom in the universe had a story to tell and each of those stories would take the age of the universe to listen before starting to listen to the next one, you would finish listen to all of them after an insane length of time which would still be nothing in comparison.

[@threethrushes]

I wonder what kind of stories atoms can tell? Sounds like a wild version of 101 Arabian Nights.

[@JohnSmith-nx7zj]

Another way of saying this is that 10^(10^(10^(10^4))) is so big that it doesn’t really matter whether your unit is Planck times or universe lifetimes. Multiplying a number of that size by 10^100 or 10^-100 has essentially no impact.

[@DadofScience]

This sequence is second only in scale and growth to my wife's ability to spend money online.

[@bogdan_ostaficiuc]

🤣🤣

[@wandrespupilo8046]

The "fancier infinitary math" he is talking about is just ordinals Vsauce has a nice video on ordinals (the title is probably something to do with "counting past infinity"), and moreover if you are already in college, there's a (not very accessible) proof of the goodstein theorem in the channel "sheaffication of G" also, i think this is only unprovable in first order arithmetic, but provable in second order, not sure

[@maxmusterman3371]

wow this is an amazing one

[@Dr_Y_Doodle]

As far as I remember this could be proven using omega-ordinals-based numbers. One can show that G. sequence for a base Omega number (Omega is by def is larger than any natural number) would eventually die the same manner in finite many steps, and thus any number with its base in N will die from -1's as well.

[@mananself]

Question: does it mean there exists another axiom (compatible with Peano's axioms) such that if we combine it with Peano's axioms, we can prove Goodstein's theorem is false? If so, can someone state that axiom? Does such an axiom look intuitive and reasonable?

[@valentinziegler1649]

Try the axiom „there is n such that g(n) does not exist“ ;) Jokes aside, any such axiom would inevitably have non-standard models only, therefore it is unlikely that the axiom would be considered „trivially true“

[@kazedcat]

Axiom of finity: All sets are finite.

[@robynsnest8668]

@1:22 you might want to check your math. 3 to the 3 to the 3 is 3 to the 9th. That would be 19683! The seven trillion is 3 to the 27! Which is 3 to 3 to 3 to 3 or 3 to the 27th. I know this from all of Graham's number videos.

[@chaoticfishpond8607]

My maths is fine, thanks. 3 to the 3 is 27. 3 to the 3 to the 3 is 3 to the 27 which is over 7 trillion.