Talk:Conway chained arrow notation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Low-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Importance
 Field:  Discrete mathematics

Examples do not seem to match description[edit]

One of the examples is 2→3→2→2. Along the way, we come across 2→3→8. The example then goes to declare that equal to 2→(2→2→7)→7. However, I think this might be a mistake. I am not an expert in Conway's chained arrow notation, but in the case of 2→3→8, the article says we would apply the rule X→(P+1)→(Q+1) == X→(X→P→(Q+1))→Q. In this case X=2, P=3, and Q=8. Applying the rule, this seems to me to indicate 2→3→8 == 2→(2→2→8)→7, not 2→(2→2→7)→7. 70.176.41.197 (talk) 06:41, 14 May 2013 (UTC)

Untitled[edit]

As it stands, this page is gibberish. I have no doubt that the equations are "correct" but they need explanation. Are the first 3 equations alternative schemes or are they all a single scheme defining one large number. -- SGBailey 22:07, 2003 Aug 27 (UTC)

They're supposed to make up a recursive definition. They're not correct, though. They don't cover the case with more than two arrows. Matthew Woodcraft

I understand Knuth's up-arrow notation which is explained. This "X>p>1=X>p" and "p>q=p^q" (using > for right arrow and ^ for exponent) explains nothing. I am inclined to empty the article unless someone can explain why I shouldn't. -- SGBailey 09:57, 2003 Aug 28 (UTC)

Fixed up the first part, however I don't get the chaining of 3 arrows as below. Dysprosia 10:06, 28 Aug 2003 (UTC)

Ach. Didn't see this page before. I sorta expected email. The eqns were correct, but although i specified, i guess i didn't make clear what X, p, and q meant. Okay, I tried working three 4-element chains, two fizzles and one probably explodes. You try it! =) Kwantus

For the non-mathies, perhaps it could help to clarify that X can in fact be anything, even another Conway chain. - Nevermind, this was added since my cache last refreshed apparently. WarDaft (talk) 07:33, 8 June 2009 (UTC)


Micropædia[edit]

(Some things which don't belong in a main page IMO but are useful to understanding.--Kwantus)

  • Every chain is equivalent to some shorter chain with the same head. That is, with any subchains X and Y, X→Y=X→n for some (usually very large) number n dependent in a nontrivial way on X and Y. This is a simple consequence of rules 1 & 2.
  • A chain beginning with two 2s stands for 4. By rules 3 and 2, 4=2→2=2→2→1. By rule 1, 2→2→(n+1)=2→2→n. By induction, 4=2→2→n for all n. By the result above, all chains 2→2→Y=2→2→n for some n.
  • A chain can be truncated ahead of any 1. By the result above, any chain X→1→Y=X→1→n for some n, and rule 1 instantly reduces that to X.

More not-clearness[edit]

" If, for convenience, we define f(n)=3→3→n then
3→3→64→2 = f64(1) (see functional powers),

  • now that doesn't follow. 3→3→64→2 = f(64→2) does however. Why should 64→2 become a superscript 64 and the 2 become a 1 inside the parentheses? If this is some special meaning of "functional powers, it isn't made clear by the link to function.
  • The remaining lines of the paragraph will remain clouded in confusion until the above is sorted out.

G=f64(4), and
3→3→65→2 = f65(1) = f64(27)
Since f is strictly increasing,
f64(1) < f64(4) < f64(27)
which is the given inequality.

-- SGBailey 15:12, 2004 Jan 27 (UTC)
You're confusing 3→3→64→2 with 3→3→(64→2). Remember, "one must be careful to treat an arrow chain as a whole." Using the first rule, with X=3→3, p=64, and q=1, we get
3→3→64→2 = 3→3→(3→3→(...→(3→3)→1...)→1)→1, with 64 copies of 3→3 before all the 1s. Those 1s can be removed, leaving
3→3→(3→3→(...→(3→3)→1))...), again with 64 copies of 3→3, which is equal to f64(1).
Factitious 11:02, September 5, 2005 (UTC)

Resolve?[edit]

"In this case the notation eventually resolves to being the leftmost number raised to some integer (usually enormous) power" This statement is pretty silly. I mean exponentiation just 'resolves' into repeated multiplication in the same way as multiplication resolves into an addition and addition really resolves into repeated incrementing (by 1). You might as well say that the notation resolves into a really long series of increments. Asteron 01:33, 25 January 2006 (UTC)

I disagree. It clarifies the structure of the result; the chained arrow notation is very hard to parse on first sight and statements like this make it easier to know what to expect. Also, it puts the chained arrow notation in its proper place as a generalization of simple exponentiation. For example, Knuth's up-arrow notation is also a generalization of simple exponentiation; would you say that it is silly to note that is a power of a? Obviously it would be ridiculous to describe either as "resolving" into repeated addition; the point is to relate them to the next most natural and already understood operation. Ryan Reich 02:00, 25 January 2006 (UTC)

Why, when, and where?[edit]

Why did Conway invent this notation?

When did Conway invent this notation?

Where (i.e., in what book or article) did Conway specify this notation? --Oz1cz 14:58, 3 June 2006 (UTC)

It's specified on page 61 of The Book of Numbers, but I don't know if that's where he first specified it. Factitious 22:30, 15 September 2006 (UTC)

New extreme-power notation proposed.[edit]

Let's consider the function Cw1 (x, n) (Conway's first sort extended function):

Cw1 (x,n) = x->x->x->...->x with n-1 arrows according to Conway chained arrow notation.


For example, Cw1 (3, 4) = 3->3->3->3; Cw1 (10, 5) = 10->10->10->10->10 etc.


Now, let's consider another function Cw2 (x) (Conway's second sort extended function):

Cw2 (x) = Cw1 (x, x).


For example, Cw2 (4) = Cw1 (4, 4) = 4->4->4->4; Cw2 (5) = Cw1 (5, 5) = 5->5->5->5->5 etc.


Now we can construct the Extreme-Power Notation:

x~1 = x;

x~2 = Cw2 (x)= x->x->x->...->x (with x-1 arrows) (incomparably larger than Graham's number!);

x~3 = Cw2 (x~2) = x~2 -> x~2 - x~2 -> ... -> x~2 (with (x~2)-1 arrows);

x~4 = Cw2 (x~3) = x~3 -> x~3 - x~3 -> ... -> x~3 (with (x~3)-1 arrows) etc.

...

x~ ~1 = x;

x~ ~2 = x~x;

x~ ~3 = (x~ ~2)~ ~2 = (x~x)~ ~2 = (x~x)~(x~x);

x~ ~4 = (x~ ~3)~ ~3 etc.

...

x~ ~ ~1 = x;

x~ ~ ~2 = x~ ~x;

x~ ~ ~3 = (x~ ~ ~2)~ ~ ~2 = (x~ ~x)~ ~ ~2 = (x~ ~x)~ ~(x~ ~x);

x~ ~ ~4 = (x~ ~ ~3)~ ~ ~3 etc.

...


Finally, lets say that Blt (x) = x~ ~ ~...~x (with x tildes (!)) (Beloturkin's function).


For example, 1 Beloturkin = Blt (G), where G is Graham's number;

1 Beloturkinion = Blt (Beloturkin);

1 Beloturkiniard = Blt (Beloturkinion).


Beloturkin 08:23, 15 September 2006 (UTC)

I added a remark along these lines at Large_numbers#Systematically_creating_ever_faster_increasing_sequences.--Patrick 13:06, 11 July 2007 (UTC)
I don't understand the point of this. Your notation doesn't construct a new paradigm. In terms of computational complexity, it is no faster than regular Chained arrow notation.

I suggest you take a gander at the "fast growing hierarchy" page. Read up on limit ordinals, the wainer hierarchy, and diagonalized functions. Then enjoy considering f_*(2) where * is the feferman-schutte ordinal. Or any large ordinal really. Even epsilon or zeta nought.

Do you really think people would be talking about Conway's chained arrow notation if all it was was a bunch of repeated and nested iterations of knuth's up arrow notation? — Preceding unsigned comment added by 216.163.254.2 (talk) 12:22, 2 September 2011 (UTC)

Order of the Rules[edit]

Is there any particular reason for the order given? Because if not, I think it should be changed from:

If p and q are positive integers, and X stands for some chain, then the following rules apply to complete chains:

  1. is equivalent to
    (with p copies of X, p -1 copies of q, and p -1 pairs of parentheses).
  2. is equivalent to X.
  3. is equivalent to the exponential expression .

to recursive form:

If p and q are positive integers, and X stands for some chain, then the following rules apply to complete chains:

  1. is equivalent to X.
  2. is equivalent to the exponential expression .
  3. is equivalent to
    (with p copies of X, p -1 copies of q, and p -1 pairs of parentheses).

with the base cases first and recursive part last, thus organizing the rules a little better (and making them just a little bit more easily comprehensible for high school students such as myself). --63.246.162.38 19:13, 14 October 2007 (UTC)

Anyone? --63.246.162.38 11:14, 23 October 2007 (UTC)
The current order is not so bad: for the interpretation of a notation like 4→3→2 (i.e. a non-trivial case) you start with applying what is now the first rule.--Patrick 16:56, 23 October 2007 (UTC)
It is non-intuitive as it doesn't fit normal recursion. If you don't know anything about recursion, you don't have much of a chance of understanding the rules and how to apply them anyway, seeing as they are a recursive definition. If you do know about recursion, the rules are very tricky to work with in strictly recursive order, much less the order in which they're given. It's discriminating against the only people who have a decent chance of understanding the rules. --63.246.162.38 01:20, 25 October 2007 (UTC)
The examples of Backus–Naur form also write the rules in top-down order. Anyway, in recursion rules A and B could both be definitions depending on A and B, so the order of the rules is somewhat arbitrary anyway.--Patrick 08:20, 25 October 2007 (UTC)
Have you ever programmed a recursive function? The conditions are generally listed in order of priority (although technically you could put them in any order you want). For example, these rules would prioritize this way in a function:
  1. If the chain ends in a 1, get rid of the last item in the chain and recurse.
  2. If the chain is of length 2, return the result of powers.
  3. Add-in: if it is a chain of length 1, return the one item in that chain.
  4. Otherwise, expand the chain and recurse.
Any other order in programming would require the use of a not (or equivalent) operator to check that another condition isn't met, which would make it superfluous. For example, in the given order, you would have to write:
  1. If the chain is greater than length 2 and doesn't end in 1, expand the chain and recurse.
  2. If the chain ends in a 1, get rid of the last item in the chain and recurse.
  3. If the chain is of length 2, return the result of powers.
  4. Add-in: if it is a chain of length 1, return the one item in that chain.
Notice how superfluous the first condition is. It's pointless to take the extra work in programming to get it to work in this order when you can much more easily get it to work in the proper order described before, and it's more readable in the proper order. --63.246.162.38 10:28, 25 October 2007 (UTC)
In the formulation of the rule, "If the chain is greater than length 2" is not needed because it is implied by the expression on the left. I added the "doesn't end in 1" condition because it is not implied by the left expression (even though it is implied by the right expression). Now all rules are valid without an implied restriction regarding priority. By the way, what do you mean by add-in?--Patrick 12:07, 25 October 2007 (UTC)
I'm really confused by what you're saying here, so please accept my apologies if I got it wrong. It seems to me that you misunderstood my point; I wasn't complaining about the lack of conditions in each case on the Wikipedia page (although I can't deny that adding "applies for q > 0" was an improvement; that did confuse me for about 5 seconds back when I first looked at the rules). I was simply pointing out that if you were to write a procedure for evaluating a chain, it would look uglier in the given order than in recursive order.
Ok, but here we just give some identities to explain the notation, and these do not require additional conditions (hence do not become uglier) depending on the order. --Patrick 12:53, 26 October 2007 (UTC)
Alright, I can see you're not about to give up on this, so I'll just put my main point forward right now, and I'll never bug you about this again. It's easier to analyze the rules the first time one sees them in proper recursive order, rather than in any other order. Make what you will of that. --63.246.162.38 12:11, 27 October 2007 (UTC)
My add-in was a case that was technically covered by the other rules, but wouldn't be covered in a programmed recursive function. If the chain is of form , the rules let you convert that into , and then raise , but the programed function doesn't see that; it just cuts of all 1's and ends up with and the function ends without having returned anything (or the compiler complains, depending on the programming language and how smart the compiler is). --63.246.162.38 10:36, 26 October 2007 (UTC)
I see, thanks.--Patrick 13:17, 26 October 2007 (UTC)

I added a fourth rule, "chain p represents number p" that was not explicitly stated. Also, I think the other order is better, because that is the order of mathematical definitions. Why is it the order of mathematical definitions? Because written that way you can see more easily that the definition is sound. BNF can iterate forever, not reaching a list of terminal symbols, but mathematical recursive definitions should be sound, and the clearer way to see that is by writing the base cases first and the recursive rules below. 81.35.123.125 (talk) 20:39, 29 April 2008 (UTC) Finally I changed the order. Now it is clear which rules are the base cases and which rules are the recursive steps, and also it is clear that the number representing a chain is well defined for any chain.

4-term chains?[edit]

The page here does not explain four-term chains; they merely give a non-explanatory example.

The way I see it, the 4th term defines a recursion. A 4-term chain such as is defined as , which is defined as

Where the number in the ellipsis is equal to c.

Am I right? What problems are there in my explanation? Is there another source I can check for information on this? ZtObOr 22:25, 9 January 2008 (UTC)

EDIT: If d is equal to 2 in this case, then it would simply be the example stated above. —Preceding unsigned comment added by Ztobor (talkcontribs) 23:03, 9 January 2008 (UTC)

The page defines where X stands for some chain. This includes chains of length 4 and more.--Patrick (talk) 00:55, 10 January 2008 (UTC)
Right. That explains a lot. Thanks. ZtObOr 00:33, 11 January 2008 (UTC)

Complete chains[edit]

In the definition, the term "complete chain" is confusing and maybe meaningless. I had to read the definition 3 or 4 times to understand it. Apparently, all chains are complete chains. Probably it would be clearer to substitute the terms "chain" and "complete chain" by the binary relation "is subchain of" or "is contained in". 81.35.123.125 (talk) 20:09, 29 April 2008 (UTC)

Finally I rewrote the definition. Also, I think it is better to change the order of the rules. When defining something in mathematics by induction, one usually writes the base case first, and then the induction rules, as in f(0)=1, f(n+1)=(n+1)*f(n). 81.35.123.125 (talk) 20:30, 29 April 2008 (UTC)

Unimaginably huge[edit]

The page states that 2^...(2^16 times)..^2 is "unimaginably huge".

Someone has marked ths claim as 'needing citation':

http://en.wikipedia.org/w/index.php?title=Conway_chained_arrow_notation&diff=286008611&oldid=251908330

There are plenty of other facts on this page that could do with citations, but requiring one for this is a bit daft. You could argue that it is understatement, or even subjective. But it is surely not a citable fact. —Preceding unsigned comment added by 81.101.133.255 (talk) 08:46, 18 May 2009 (UTC)

Agreed, I even laughed out loud at seeing that. I'll remove it for now, although one might want to look into rephrasing this and other parts of the article. 83.227.162.5 (talk) 21:46, 19 May 2009 (UTC)

ANY number?[edit]

I understood Knuth's up arrow notation after a bit of fiddling. Impressive how 1 arrow can so dramatically increase the value of the number. Conway arrows, however, I do not understand. I will eventually, if I keep at it, but right now, that's not really my concern. My question is, can this notation represent any large number, or just extraordinarily mind bogglingly large powers? —Preceding unsigned comment added by Mavrisa (talkcontribs) 02:34, 28 October 2009 (UTC)

Trivially, every integer can be considered a chain of length one. However, all chains of length greater than one are nontrivial powers of the first element. That is, any chain m->X (where m is an integer and X is a subchain) is equal to mn for some n. Therefore Conway notation can only be used to express large powers of integers.
For longer chains, an even more limited class of functions can be expressed. Graham's number, for example, is just an extremely large power of 3, so it could be expressed as 3->X for some chain X, but there is no convenient X to use here. Furthermore, since Graham's number is equal to 3^^^...^3, we could express it as 3->n->3 for some n. Unfortunately, n here is still astronomically large. In order to get numbers large enough, we really need to use a chain of length four, but chains of length four are usually too big! The chain will be far too large if the last element is greater than 2, so we know it must have the form 3->n->3->2, but unfortunately, we find that 3->3->64->2 < G < 3->3->65->2. That is, there is no concise chain that will equal Graham's number.
To summarize, Conway notation is only useful for certain classes of numbers. In general, the longer the chain, the fewer the numbers that can be expressed exactly. However, for loose approximations, Conway notation is often fine. Eebster the Great (talk) 05:14, 28 May 2010 (UTC)
I for one am not clear on what exactly constitutes a chain. For example, can
3->3->(3->3->(...(3->3->(3->3->4))...) with sixty four (3->3->)'s
be considered a chain or nested sub-chains? Its definitely in chained arrow notation. AFAIK, its irreducible as is. And its exactly equal to Graham's Number. Chasrob (talk) 12:50, 28 May 2010 (UTC)
Graham's number is 3->3->(3->3->(...(3->3->(3->3->4))...)) (with sixty-four '3->3->'s), which is a fairly concise expression using ellipses and some added English words; however, the actual expression in Conway arrow notation contains 128 arrows, which is not so concise. EDIT: Of course this could also be written in iterated function notation as (3->3->)644, which is even more concise, but that's also not purely in Conway's notation. — r.e.s. (talk) 16:04, 28 May 2010 (UTC)

Locating n-arrow chains in the fast-growing hierarchy[edit]

I've seen it conjectured that for any fixed p ≥ 3, the growth-rate of the function of n represented by the n-arrow chain pp→...→p is approximately that of fω2 in the fast-growing hierarchy, and, similarly, that the growth-rate of the function of n represented by the n-arrow chain nn→...→n is approximately that of fωω. (E.g., see Section 5 in this posting.) Can anyone cite sources for proofs adequate to allow including something along these lines in the article?
r.e.s. (talk) 16:45, 2 June 2010 (UTC)

Although I haven't been able to find a "citable" source for this, I believe I can show fairly rigorously that the n-arrow chain nn→...→n is less than fω2(n) for all n, disproving the mentioned conjecture re fωω.
r.e.s. (talk) 06:06, 16 June 2010 (UTC)

Notation references[edit]

Is anyone aware of an additional reference (besides The Book of Numbers) from any of Conway or Guy's work? I noticed above that this was asked in 2006 and it got no reply. Surely there is more somewhere besides a single paragraph on page 61 in The Book of Numbers. Chasrob (talk) 13:53, 14 August 2010 (UTC)

An exponential of the Conway chained arrow notation?[edit]

Has any mathematician suggested or used an exponential notation of conway's chained arrow notation? By which I mean, as 1010 = 10 × 10 × 10 × 10 × 10 × 10 × 10 × 10 × 10 × 10. It would display 10 → 10 → 10 → 10 → 10 → 10 → 10 → 10 → 10 → 10 as equaling 10 & it's notation to 10. Nagelfar (talk) 23:27, 14 September 2011 (UTC)

Definition and overview[edit]

Equation 4b: if q is 2 (or more), don't there need to be 2 (or more) q's at the end of the expansion, to be complete??? Chasrob (talk) 01:55, 7 August 2012 (UTC)

Whoops, my bad, I see:). Neato.Chasrob (talk) 01:20, 27 August 2012 (UTC)
Wouldn't it be logical to use the recursive steps 4a and 4b instead of step 4 in the example section? You wouldn't have to worry about bolding, for one reason.Chasrob (talk) 00:38, 28 November 2012 (UTC)

Question out of curiosity:[edit]

if g(x) is Graham's function, if n is a natural number, is there an n for which:

g(n) < 3→3→n→2?

It seems like it may be possible with an incredibly huge n. Is it provable? Do people agree? If so, can anybody find what value the n has to be (approximately). This question has been bugging me for weeks! — Preceding unsigned comment added by AlexTMM (talkcontribs) 17:08, 15 December 2012 (UTC)

There is no such n, according to the section Conway_chained_arrow_notation#Systematic_examples: letting f(n) = 3→3→n→2,
f(n) = 3↑f(n-1)3, with f(1) = 3↑3.
But, by definition, writing g(n) = gn,
g(n) = 3↑g(n-1)3, with g(1) = 3↑↑↑↑3;
consequently, f(n) < g(n) for all positive natural numbers.
r.e.s. (talk)

Of course, I've been looking at the problem the wrong way round. Thank you for enlightening me, and for your very quick answer! — Preceding unsigned comment added by 78.129.14.172 (talk) 00:20, 18 December 2012 (UTC)

Extender notation?[edit]

For example A-->-->B will equal A-->A...-->A-->A with a chain length of B. If B=1, then it will equal A — Preceding unsigned comment added by Bubby33 (talkcontribs) 21:02, 10 May 2014 (UTC)

Conway/Guy?[edit]

Shouldn't this article be Conway/Guy chained arrow notation? They were co-authors of the book in which it first appeared, yes? Chasrob (talk) 18:13, 29 October 2014 (UTC)

The notation which is extend Conway's chained notation[edit]

Can we define:

Thus, 43 = , is much greater than Graham's number, is it right?

And that 0a = 1, 1a = a, 2a = aa.

Besides, how big is googolplexgoogolplex?

Another notation[edit]

We can define a {1} b as ab, :

So if n = googolplex, than n {n} n is very large, much larger than n [n] n in hyperoperation. — Preceding unsigned comment added by 140.115.138.5 (talk) 06:02, 5 November 2014 (UTC)

It's not well-defined, as the operations are not associative. — Arthur Rubin (talk) 19:20, 6 November 2014 (UTC)

Connections between the chains and any mathematical operations?[edit]

Just for a thought - can the numbers in the chain be somehow resolved to some operation which can be applied? Especially, it seems that the last member of a chain stands for the number of applications of a certain operation on the remaining members: in a chain of length 1, it is the number of times zero has to be incremented; in a chain of length 2, it is the number of times the first number has to be multiplied with itself; in a chain of length 3, it is the number of Knuth arrows which has to be put between the first and the second member. Can a chain of length 4 be written as some fourth-member-fold operation on the first three members? And, generally, can a chain of length n be written as an n-th-member-fold operation (depending on n) on the first n-1 members? And if the answer is yes, is there any algorithm to get the operation in question (that is, to say which operation is meant) without actually calculating out the chain?--85.177.249.99 (talk) 12:17, 15 March 2015 (UTC)

The background of my question, by the way, is another question: can this notation be sensibly extended to non-natural numbers as chain members? Zero? Negatives? Rationals? Or even complex numbers?--85.177.112.83 (talk) 22:55, 17 March 2015 (UTC)