FANDOM


 
(One intermediate revision by one user not shown)
Line 126: Line 126:
 
[[User:p進大好きbot|p-adic]] 03:49, March 26, 2020 (UTC)
 
[[User:p進大好きbot|p-adic]] 03:49, March 26, 2020 (UTC)
 
:Do you mean [https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf this article]? I'm not confident about how does this TR(n) compare with TREE(n), but if they're different, then possibly there is no explicitly given source by Friedman himself. At least, the [https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem Wikipedia article] doesn't have the source for the definition. It's okay to clarify it, in my opinion. [[User:Ikosarakt1|Ikosarakt1]] ([[User_talk:Ikosarakt1|talk]] ^ [[Special:Contributions/Ikosarakt1|contribs]]) 06:38, March 26, 2020 (UTC)
 
:Do you mean [https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf this article]? I'm not confident about how does this TR(n) compare with TREE(n), but if they're different, then possibly there is no explicitly given source by Friedman himself. At least, the [https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem Wikipedia article] doesn't have the source for the definition. It's okay to clarify it, in my opinion. [[User:Ikosarakt1|Ikosarakt1]] ([[User_talk:Ikosarakt1|talk]] ^ [[Special:Contributions/Ikosarakt1|contribs]]) 06:38, March 26, 2020 (UTC)
  +
  +
:: Thank you. Exactly, I meant it. In that case, is there any reason why "TREE" in the sense of Friedman is believed to be defined as the one in the article? In other words, is there a possibility that what Friedman calls "TREE" is different from the TREE function in the article? In that case, I am afraid that there is no justification of the results (e.g. the termination, the growth rate, and the specific estimations) of TREE.
  +
:: [[User:p進大好きbot|p-adic]] 06:52, March 26, 2020 (UTC)
  +
  +
:: I think that [https://cs.nyu.edu/pipermail/fom/2006-March/010279.html this] is the first source. Then the definition in the article is correct as long as the ambiguous "homeomorphically embeddability" means the other condition in the source, and I guess that the description in wikipedia (stating TREE is TR) is non-trivial because TR refers to wider cases. I will update the article later.
  +
:: [[User:p進大好きbot|p-adic]] 07:12, March 26, 2020 (UTC)

Latest revision as of 07:12, March 26, 2020

Archive 1

should we redirect TREE(3) to TREE sequence? Edit

discuss here. i think yes. Cookiefonster (talk) 01:31, February 17, 2015 (UTC)

Should we redirect TREE(3) to TREE sequence?
 
15
 
17
 

The poll was created at 11:22 on February 20, 2015, and so far 32 people voted.

I saw that for example Fish's numbers has been added to the full list twice. So, could other values of TREE(k) be in the list? I mean there certainely is values of k at wich TREE(k) would overpower for example Meameamealokkapoowa Oompa of Loader's Number, that would be cool to add a such number 

Fluoroantimonic Acid (talk) 18:52, June 4, 2015 (UTC)Trifluoromethanesulfonic Acid

TREE(3) is the only value that is particularly notable, since it's the smallest nontrivial value of TREE(n) - TREE(1) and TREE(2) are 1 and 3 respectively. the next values aren't really in a different realm of numbers from TREE(3) if i'm not mistaken. the fish numbers are different, since each of them are really separately devised values and not just different outputs of a single function. Cookiefonster (talk) 19:24, June 4, 2015 (UTC)

Another thing is that other specific values of TREE(n) have never been (afaik) considered, so there is no reason to put different values of TREE into the list. LittlePeng9 (talk) 20:53, June 4, 2015 (UTC)

\(ACA_0+\Pi_2^1-BI\)Edit

"How strong is \(ACA_0+\Pi_2^1-BI\)?" In another word, what's the least ordinal \(\alpha\) such that \(f_\alpha(n)\) eventually outgrows all functions provably recursive in \(ACA_0+\Pi_2^1-BI\)? {hyp/^,cos} (talk) 03:07, July 7, 2015 (UTC)

Let$ \omega[n] = \Sigma(n) $. Now$ f_\omega(n) [>] \Sigma(n) $ and since$ f_\omega $ is above recursive, the answer is$ \alpha = \omega $. To see that it's least such ordinal, observe that all ordinals less than$ \omega $ are natural numbers and FGH for them doesn't depend on FS.
I think more interesting question would be: "What's the least ordinal existence of which cannot be proved by  $ ACA_0+\Pi_2^1-BI $?"
Ikosarakt1 (talk ^ contribs) 12:14, August 2, 2015 (UTC)
Finding the PTO of \(ACA_0+\Pi_2^1-BI\) is a research-level problem for sure. -- vel! 13:20, August 2, 2015 (UTC)
I would guess that the PTO of \(ACA_0+\Pi_2^1-BI\) is \(\theta(\Omega^{\omega},0)\), but I do not have a reference for that. Deedlit11 (talk) 06:33, August 5, 2015 (UTC)

Where does TREE(3) fit into the heirarchy on Bowers' infinity scrapers page? Edit

Jonathan Bowers (Hedrondude), best known for the BEAF notation has a webpage which expands upon the array notation to define large numbers: http://www.polytope.net/hedrondude/scrapers.htm

It's clear from reading the available online information that TREE grows more slowly than Rayo's and other functions which are arbitrarily defined as largest number that is theoretically writeable using an n-state Turing machine or a mathematical language with n symbols.  So, TREE(3) is smaller than Oblivion, Rayo's number, etc.  But what about large numbers that have been written clearly, and not based on a linguistic algorithm?  

I have read that TREE(3) is smaller than Loader's number .  Loader's number is computable; the README for Loader's code states that this is because because the Calculus of Constructions is not Turing-complete, so the program will eventually terminate.  But Loader's number is still defined using a concept of "The largest number that can be stated in the language L in less than N symbols", where, in this case L is the Calculus of Constructions.  Using "less than N symbols" in the definition of a function allows for larger numbers than any other known technique.

But what about numbers that use an already-defined mathematical language (like BEAF) and a fixed number of symbols?  Numbers such as meameamealokkapoowa oompa?  Is TREE(3) smaller than meameamealokkapoowa oompa, or any other number defined using an expansion of up-arrow notation without the "less than N symbols" trick?  I suspect that TREE(3) is smaller than oompa, but since I have trouble reading the notation of the fast-growing heriarchy, I would be curious to know approximately where it fits into Bowers' infinity scrapers page.  For example assuming meameamealokkapoowa oompa beats it, is TREE(3) also smaller than a Gongulus?  Bowers does not resort to using the phrase "defined in fewer than N symbols" until the definition of Oblivion at the very bottom of the page.

BEAF did not well-defined above the tetrational arrays. AarexWikia04 - 01:26, October 1, 2016 (UTC)
I think TREE(3) can be expressed in Sublegion BEAF \(\841 (Talk)\) 12:27, October 13, 2016 (UTC)
I can argue with AarexWikia04, saying that pentational arrays are also well-defined with work of Deedlit11 and Ikosarakt1. So, I dunno if pentational arrays should beat TREE (3), and I think that they don't. —Preceding unsigned comment added by Tetramur (talkcontribs) 11:23, May 2, 2019 (UTC)

Value of Weak Tree FunctionEdit

I think that this section:

A larger lower bound has since been found. Define \(\text{tree}_2(n)=\text{tree}^n(n)\) and \(\text{tree}_3(n)=\text{tree}_2^n(n)\). Then \(\text{TREE}(3) > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\). The latter expression is equal to treetreetree...tree(n)...(n)(n)(n) with n layers, where \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\).

is more accurately (and helpfully) written as this:

A larger lower bound has since been found. Define \(\text{tree}_2(n)=\text{tree}^n(n)\) and \(\text{tree}_3(n)=\text{tree}_2^n(n)\). Then \(\text{TREE}(3) > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\). The latter expression is equal to treetreetree...tree(n)...(n)(n)(n) with \(n^2\) layers, where \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\).

I notice that \(\text{tree}_3(n)\) creates a tower of n \(\text{tree}_2(n)\)s, each level of which creates a tower of \(\text{tree}_2(n)\) \(\text{tree}\)s.  The pattern shows that \(\text{tree}_m(n)\) creates a tower of \(n^{m-1}\) \(\{tree}\)s following FGH's \(f_2\)(n) growth rate (in the number of \(\text{tree}\) iterations.



24.163.58.140 13:01, December 24, 2016 (UTC)


treem(n) equals treem-1n(n); if you then expand the latter expression out in terms of treem-2(n), you get a tower of functional exponents of height n. Expanding it further to treem-3(n) would get you an ENORMOUS tower of functional exponents, much higher than n^2 or n^3; the actual height of the tower would be the previous exponential tower of treem-2(n), but height one less (so n-1). The value of that exponential tower of n-1 treem-2's would get you how high the exponential tower of treem-3 has to be. So things are a little more complicated. Deedlit11 (talk) 14:30, December 25, 2016 (UTC)

How much larger is TREE(4) than TREE(3)?172.58.107.8 01:06, January 26, 2017 (UTC)

Approximately TREE(4) larger 217.194.207.20 09:43, January 27, 2017 (UTC)

Only TREE(3)?Edit

Why not TREE(4) or even TREETREE...(TREE10100(1000)(1000)? (TREEn+1(k)=TREEnk(k)) 80.98.179.160 19:39, November 14, 2017 (UTC)

One can of course talk about the values of TREE(n) for larger inputs. TREE(3) was notable in that it was the first value which jumped up really high: TREE(1) = 1, TREE(2) = 3, and TREE(3) requires going beyond the Small Veblen Ordinal to bound it in the fast-growing hierarchy using a reasonable number of symbols. Deedlit11 (talk) 03:43, November 17, 2017 (UTC)

TREE(3) hits mainstream media! Edit

Popular Mechanics recently published an article on TREE(3) here: http://popularmechanics.com/science/math/a28725/number-tree3 (note: partially paywalled) --Ixfd64 (talk) 06:00, January 15, 2018 (UTC)

TREE(3) had already hit mainstream media in my opinion after the Numberphile video, but it's nice to know it is sinking it's roots into other places, (pun intended). Edwin Shade (talk) 16:12, January 15, 2018 (UTC)

Growth rate of TREE functionEdit

It's solved here, page 39.

Definitions: Labeled tree A is homeomorphically embeddable into B if there exists such an injection f from nodes of A to nodes of B that

  1. For any node s and t of A, f(the nearest common ancestor of s,t) is the nearest common ancestor of f(s), f(t).
  2. For any node t of A, (the label of t, the label of f(t)) is "in certain ordering".

If the labels of nodes are in a well-partial ordering (i.e. the "in certain ordering"), then the trees are also in a well-partial ordering by homeomorphically embedding. Further, if the labels of nodes have order type \(\alpha\), then the corresponding trees have order type \(\le\theta(\Omega^\omega\alpha,0)\).

For TREE(n), the labels can be 1,2,...,n, and "in certain ordering" means "equal", so the labels form a well-partial ordering of type n. So the labeled trees have order type \(\le\theta(\Omega^\omega n,0)\). Here shows an ordering of \(\theta(\Omega^\omega n,0)\), so \(\text{TREE}(m,n)\approx f_{\theta(\Omega^\omega m,0)}(n)\) and \(\text{TREE}(n)\approx f_{\theta(\Omega^\omega\omega,0)}(n)\).

Now we can say about upper bounds of TREE(3), e.g. \(f_{\theta(\Omega^\omega\omega,0)}(3)\). {hyp/^,cos} (talk) 04:03, May 31, 2018 (UTC)

I have discussed it with Plain'N'Simple on the estimation using the upperbound of the ordinal types, but could not derive the upperbound of TREE(3) in your way. How could you verify the upperbound of the value from the upperbound of the ordinal types? Please read issues in the thread here starting from my comment "That function employs the 2-adic encoding...". The upperbound of the ordinal types do not give even an upperbound of the growth rate using a canonical system of fundamental sequences. If you have some unwritten reasoning, please tell me. If you just mistook the argument, please clarify it since there are many reasonless statements on the upperbound of TREE(3), which might have been spread from this community.
p-adic 04:13, October 25, 2019 (UTC)

Weak tree(3) bound by mgiroux and DeedlitEdit

It origins here, but I have calculated again and result a different value.

4. (()()())
5. ((()())())
6. ((((()()))))
7. ((((())(()))))
8. ((((((())))()))) [Let tree 1 = () and n+1 = (n), then this can be written as (((4 1)))]
9. (((3 1)))
10. (((2 1)))
11. (((1 1)))
12. ((5 5))
13. ((7 4))
16. ((4 4))
17. ((12 3))
26. ((3 3))
27. ((23 2))
48. ((2 2))
49. ((46 1))
94. ((1 1))
95. (47 47)
96. (49 46)
99. (46 46) [From (47 47) to here it takes 4 steps]
100. (54 45)
109. (45 45) [From (46 46) to here it takes 10 steps]
110. (65 44)
131. (44 44) [From (45 45) to here it takes 22 steps]

Generally, from (48-n 48-n) to (47-n 47-n) it takes \(3\cdot2^n-2\) steps, so from (47 47) to (1 1) it takes \(\sum_{n=1}^{46}(3\cdot2^n-2)=422212465065886\) steps.

422212465065981. (1 1)
422212465065982. 422212465065982
844424930131963. 1

So my calculation results tree(3) ≥ 844424930131960. {hyp/^,cos} (talk) 15:02, October 29, 2018 (UTC)


What is the first source? Edit

The article refers to the following two sources, but they are obviously non-first sources. In the archive page of this talk page, Ikosarakt1 states that Chapter 11 of "ENORMOUS INTEGERS IN REAL LIFE" might be the first source, but it seems to be a different sequence. Could someone tell us the first source? Otherwise, I will clarify in the article that there is no source.

p-adic 03:49, March 26, 2020 (UTC)

Do you mean this article? I'm not confident about how does this TR(n) compare with TREE(n), but if they're different, then possibly there is no explicitly given source by Friedman himself. At least, the Wikipedia article doesn't have the source for the definition. It's okay to clarify it, in my opinion. Ikosarakt1 (talk ^ contribs) 06:38, March 26, 2020 (UTC)
Thank you. Exactly, I meant it. In that case, is there any reason why "TREE" in the sense of Friedman is believed to be defined as the one in the article? In other words, is there a possibility that what Friedman calls "TREE" is different from the TREE function in the article? In that case, I am afraid that there is no justification of the results (e.g. the termination, the growth rate, and the specific estimations) of TREE.
p-adic 06:52, March 26, 2020 (UTC)
I think that this is the first source. Then the definition in the article is correct as long as the ambiguous "homeomorphically embeddability" means the other condition in the source, and I guess that the description in wikipedia (stating TREE is TR) is non-trivial because TR refers to wider cases. I will update the article later.
p-adic 07:12, March 26, 2020 (UTC)
Community content is available under CC-BY-SA unless otherwise noted.