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^45, please don’t freak out.

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

  1. a^b = ab
  2. a^n1 = a (for n > 1)
  3. a^nb = a^n-1(a^n(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^nb = 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 = 22 = 4, and 2^4 = 24 = 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 = 333 = 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^nn 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.