TL;DR unless you are a math freak. I will describe a numerical sequence and ask you to guess its ultimate outcome. Does it increase continually, or settle down to a fixed number of just stop?
In this case we start with the number 21, but you could start with any number including a googolplex. We write using only numbers 2 or 1 as T_2 = 2^{2^2} +2^2 + 1
which I will call the 2-tableau.
We construct the 3-tableau by replacing every instance of 2 in the 2-tableau by a 3 and then subtracting 1: T_3=3^{3^3}+3^3
which actually adds up to 7,625,597,485,014. In a similar way, construct the 4 tableau by replacing every instance of 3 in the 3-tableau by 4 and then subtracting 1. However in the process, we are allowed only addition, so we have to replace 4^4-1 by 3\times4^3+3+3\times 4^2+3\times4+3 using the formula \frac{4^4-1}{4-1}=4^3+4^2+4+1. This and analogous steps are crucial in understanding the ultimate outcome. Then T_4=4^{4^4}+3\times 4^3+3\times4^2+3\times 4+3
I won’t even try to evaluate this numerically. Continue this process to get T_5=5^{5^5}+3\times 5^3+3\times 5^2+3\times 5 +2
Only the 4’s change to 5 and always subtract 1. Since 5^5=3125, and 5^{3125} is already incomprehensibly large, so is T_5. Continue with T_5,T_6,...,T_{googolplex},....
What do you think will happen in the long run?
It eventually gets to 0 and stops. Those -1 terms eventually overwhelm everything. But the only proof I am aware of uses transfinite induction based on \epsilon_0 by noting that if in T_n, you replace each instance of n by \omega, call it T_{n,\omega} then T_{n+1,\omega}<T_{n,\omega} (strictly less than) and there can be no infinite strictly descending sequence of ordinals. Therefore the sequence must stop.
No, it is basically from the logic of well-ordered sets. Quite astonishing, really. I once tried to work out the number of steps required with a starting number of only 5 and it was something like 10^20. But it is basically an exercise in ordinal arithmetic, which is part of set theory. Has nothing tdo with calculus or linear algebra or any subject that anyone but a math student would ever encounter.
I vaguely remember hearing of this one. Isn’t the “time” it takes to get there unfathomably long? Like we don’t know how big a number you have to get to before it even starts noticeably decreasing?
I would say it is fathomable in the sense that you can use ordinals to prove the claim and estimate/put bounds on the length of the sequence and compare it to other “large numbers”, like @Hari_Seldon outlines.
Yes, of course it is unfathomably long. But the amazing thing is that it seems to increase for an unfathomably long time to an unfathomably large number. But then it begins to decrease, very slowly and eventually stops.
You actually can prove this happens for each individual integer but there is no general argument without \epsilon_0 induction that it always does. By the way, \epsilon is the largest ordinal you can name using only \omega and ordinal addition, multiplication and exponentiation.
Seems kind of small? I need to check this. But by “fathomable” I meant that we should be able to write down the total number of steps, how many steps it takes until it starts decreasing (halfway through?) and how big it gets all in terms of a fast-growing hierarchy of functions. There are some explicit formulae on Wikipedia (which seem to indicate the number of steps starting with 5 is more than 10^{10^{10^{19727}}})
Short answer is, see here: Goodstein's theorem - Wikipedia
Should link to a section “Sequence length as a function of the starting value” containing some references re. the growth rate and values, as well as a little table
I’m not clear on what you’re saying, here… It sounds like any n-tableau should only contain n, no other explicit integer, but that expression contains both 3s and 4s. Is that mixed expression part of the 3-tableau or the 4-tableau?
T_n can contain any number =< n. So T_2 has 2’s and 1’2. T_3 any of 1.2. Or 3. But in going from T_n to T_{n+1}, all instances of n are replaced by n+1, but all smaller numbers do not change. Then subtract 1.
NB that’s true enough, but first consider e.g. the sequence starting with 4. Then T_3 = 3^3 - 1 already has all exponents below 3. Then T_{23} = 2 \cdot 23^2. Going with this, you have to add another 23 to the base, then (more than) twice that, etc., so, adding all this up (24\cdot 2^{24}-1 = 402563183) it takes T_{402563183}=402563183^2 before we even get to the linear part. Doing the same calculation again, we get to zero at base 24\cdot 2^{24}\cdot2^{24\cdot 2^{24}}-1.
We can do a similar calculation for 5, but I think we see that we have left 10^{20} far behind despite the lack of an initial blow-up; a power of 2, let alone 3, is enough to force the rest of the sequence to be long (longer than a simple power of 10, I mean: we get a (short) tower of powers).
You are correct. I did a similar computation starting with 4 and got similar results. I cannot imagine what made me think that 5 gave a reasonable result. I wonder what my illustrative example of 21 would give. And yet the argument with epsilon_0 is almost trivial.
Starting with 21=2^{2^2}+2^2+1 the final base is f_{\omega^\omega}(f_\omega(f_0(3)))-1=f_{\omega^\omega}(f_4(4))-1, if I have understood the general argument. Now f_4(4) is pretty big in the day-to-day sense, but we can write it as a stack of 7 or so powers. However, now this pretty big number is the input to a much faster-growing function, so we can ask ourselves how we want to notate or try to comprehend the resulting value. It is a finite number which is perfectly computable, though.