Talk:Conway chained arrow notation

From Wikipedia, the free encyclopedia

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

Contents

[edit] Micropædia

(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 (usu 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.

[edit] More not-clearness

" 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)

[edit] Resolve?

"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 a \uparrow b 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)

[edit] Why, when, and where?

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)

[edit] New extreme-power notation proposed.

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

Cw1 (x) = 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_sequenceshttp://en.wikipedia.org../../../../articles/l/a/r/Large_numbers.html#Systematically_creating_ever_faster_increasing_sequences.--Patrick 13:06, 11 July 2007 (UTC)

[edit] Order of the Rules

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. X \to p \to (q + 1) is equivalent to X \to ( X \to ( \dots (X \to ( X ) \to q)\dots ) \to q ) \to q
    (with p copies of X, p -1 copies of q, and p -1 pairs of parentheses).
  2. X \to 1 is equivalent to X.
  3. p \to q is equivalent to the exponential expression pq.

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. X \to 1 is equivalent to X.
  2. p \to q is equivalent to the exponential expression pq.
  3. X \to p \to (q + 1) is equivalent to X \to ( X \to ( \dots (X \to ( X ) \to q)\dots ) \to q ) \to q
    (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 p, the rules let you convert that into p \to 1, and then raise p1, but the programed function doesn't see that; it just cuts of all 1's and ends up with p 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.

[edit] 4-term chains?

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 a \rightarrow b \rightarrow c \rightarrow d is defined as a \rightarrow b \rightarrow c \rightarrow ((d-1)+1), which is defined as a \rightarrow b \rightarrow (a \rightarrow b \rightarrow (a \rightarrow b \rightarrow(...(a \rightarrow b)...)\rightarrow (d-1)) \rightarrow (d-1))

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 (talk • contribs) 23:03, 9 January 2008 (UTC)

The page defines X \to p \to (q + 1) 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)

[edit] Complete chains

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)