Chained recursion (like Conway arrows, but better!)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

arbiteroftruth
Posts: 481
Joined: Wed Sep 21, 2011 3:44 am UTC

Chained recursion (like Conway arrows, but better!)

I was thinking about chained arrow notation and how interesting it is, but it bothered me how it's simultaneously too coarse to exactly represent something like Graham's number, and too weak to even reach ω2 in the fast-growing hierarchy. So I thought I'd try to come up with something better, and here's what I've got.

A non-empty chain begins with '|' and consists of a string of numbers each separated by either '|' or '→'.
Let X be an arbitrary, possibly empty chain.
Let Y be a non-empty string of numbers separated only by '→'.
[axioms]
|n=n+1
X|n=X→n
X|n→0=n
X|n→(m+1)=X|(X|n→m)
X|Y→n→0=X|n
X|Y→n→(m+1)=X|Y|Y→n→m
[\axioms]

The idea is that a | represents treating the sub-chain on the left as a function that appends the input onto itself with a →, and a continuous string of numbers using only →'s after a | represents increasing layers of diagonalization over that function, with the whole thing built on the base case of the successor function. A final →-only string with only 2 numbers represents primitive recursion with the first number being the seed value and the second being the iteration count. Each additional number in the final →-only string represents another layer of diagonalization.

Examples:
|n→m=n+m (proof by induction: |n→0=n, and if |n→m=n+m then |n→(m+1)=|(|n→m)=|(n+m)=n+m+1)
|n|0→m=n*m (the proof is similar)
|n|0|1→m=nm
|n|0|1|1|1|...|1→m=n↑pm (indexed Knuth up-arrows) where p is the number of 1's in the chain. More compactly:
|n|0|1→m→p=n↑pm

I had some stuff in here about replicating Conway arrows that I've since realized was incorrect. A two-element Conway chain is just exponentiation, which is shown above. A three-element Conway chain is the up-arrow sequence, which is also shown above. A four-element Conway chain p→q→r→s would be:
|p|0|1→q|1→r→(s-1)
But because of that -1, there's no way to exactly replicate longer Conway chains. But you get a similar behavior with this format:
|a0|0|1→a1|1→a2|...|1→an|0
That's how the pattern goes if you just ignore those -1's that show up. It's equivalent to Conway arrows where you wait for the final term to be 0 before removing it, rather than removing it at 1.
So one function with a growth rate about the same as the Conway chain n→n→n→...→n with n n's would be:
|n|0|1→n→0→(n-1)
Because that strings out n-1 copies of "1→n" separated by |'s and followed by "|0", which exactly matches the format above.
[\Edit]

Graham's number is exactly
|3|0|1→3|4→64
Because |3|0|1→3→n is 3↑n3, and this function of n is seeded with 4 and iterated 64 times.

I don't yet have a proof, but I believe this notation is first dominated by ωω in the fast-growing hierarchy. That is, ωω has a similar growth rate as |n→n→...→n with n n's.

Of course, you could diagonalize over the length of such chains, and then diagonalize over whatever notation you come up with for that, and so on, but you've got to stop at some point, and I'm pretty satisfied with this notation.