Arrow by Knuth/half-alive

On an unrelated note, check out Arrow by half-alive, one of the best songs ever.

Just for simplification, instead of the arrow symbol, I will use the ^ symbol, so 3^^8 = 3↑↑8. If you see 3^⁴5, please don’t freak out.

Up-arrow notation is a hyperoperation devised by Donald Knuth in 1976. a^ⁿb can be defined with three simple properties:

1. a^b = a^b
2. a^ⁿ1 = a (for n > 1)
3. a^ⁿb = a^^n-1(a^ⁿ(b-1)) (for n > 1, b > 1)

Let’s go over them, one by one.

First property: pretty simple. With one up arrow, it’s just exponentiation.

Second property: still simple. If b = 1, a^ⁿb = a, as long as n > 1.

Third property: actually simple if you understand the basics. Donald Knuth stated that, for a^^…^^b with n ^’s, it is equivalent to a^^n-1(a^^n-1(a^^n-1(…^^n-1(a^^n-1a)…))) with b a’s. Using a form of recursion, the third property can be reformed into the statement that Donald Knuth proposed.

What are some examples of up-arrow notations?

Let’s do the first example: 2^^3. That’s 2^2^2, and it’s not (2^2)^2, and it’s 2^(2^2). 2^2 = 2² = 4, and 2^4 = 2⁴ = 16. The second: 3^^^3, which is also familiar, isn’t it? We went over it in the Graham’s Number post. With 3^^^3, that’s 3^^(3^^3), which is already huge. 3^^3 = 3³³ = 3^27 = 7625597484987, or 7.6 trillion. For the outer double arrow, that’s 3^3^3^3^…^3^3^3 with 7.6 trillion 3’s.

Yeah. It’s big.

In fact, the function n^ⁿn is larger than all primitive-recursive functions, which… I have no idea.

That’s detail.

My third Favourites post is coming soon, and I will see you then.