The notorious TREE(3). Is it possible to actually comprehend how large this number is? And how is it proven that three inserted in the TREE function outputs a finite number instead of just being infinity?
>>16910744>Is it possible to actually comprehend how large this number is?There's no known upper bound so any analogy you could come up with is meaningless. If you came up with some fuckhuge nesting analogy that dwarfs TREE(3) you wouldn't have any way of knowing you exceeded the target.>And how is it proven that three inserted in the TREE function outputs a finite number instead of just being infinity?https://en.wikipedia.org/wiki/Kruskal's_tree_theorem
i still cannot fathom the definition of TREE(), no description makes any fucking sense. i've read the wiki article several times over the years and have made no headway on what the fuck makes it grow so fast.
>>16910781Since its values on 1 and 2 are trivial, and you probably only want to know why TREE(n) is big in the first place, I don't think that any framing of "grow" is helpful.You're not really interested in why something "grows" here. Per fixed n (say n=3) there's nothing that grows, there's just a construction that gives a bound. Like if you ask who's the person in London who can do the most number of cartwheels and which number is it, there's no "growing" involved. You really just want to start with getting an intuition why it happens to be finite at all. And for this I guess you gotta read the theorem anon linked above.
>>16910781it has something to do with circuit topology imo.
>>16910801nigger, i'm just trying to understand what is being enumerated
>>16910870It's not an enumeration is the sense that there's a fixed starting point and you count through them.The return value m is the size of the largest sequence of trees, where both the trees and the sequence is subject to certain requirements.Like say you got 70 friends and familiars. {tom, ralph, bob, marry, carl, ludwig, yerimiah, zack, xena, micky, max, ...}Say you define a function f where m=f(you) is the longest chain of your friends name where each name's letter in the sequence starts with the last letter of the previous name.So one legal sequence would bemarry, ralphand maybe that's it because there's nobody who starts with h.One legal sequence would betom, marry, yerimiahand we run into the same issueOne legal sequence would betom, max, xena, ...and maybe there's an Adam in the 70 or whatever and you can actually get into an infinite sequence with max, xena, adam.Or maybe there's an andy and you can only dotom, max, xena, andy, yerimiahand the longest sequence is m=5.Then f(you)=5.The return value on 3 is m=TREE(3) and it's define as the longest sequence of some trees, and it's constructive to be extremely loose (some mild conditions on rooted trees, of which there are many) but by that theorem it's actually provably not something unending.You're "enumerating" the trees, but like with the names, it's defined with a max and there's no given starting point. It's implicitly defined as "that m whatever the max is". If someone can give you the correct long sequence , then you could "enumerate the sequence", but that's not necessary to understand the function definition.
constructed to be extremely loose
