The logician Harvey Friedman is an expert on infinity, but he also likes large finite numbers. Here's a cool thing he showed. Say you have a finite alphabet to write with. How long can a word be if no consecutive block of letters in this word, from the nth to the (2n)th, is allowed to appear as a subsequence inside a bigger block from the mth letter to the (2m)th?
If you have just one letter, this is the longest it can be:
AAA
If you have two, this is the longest it can be:
ABBBAAAAA
If you have three letters in your alphabet, there's still a finite upper bound on how long the word can be. But... it's incomprehensibly huge!
When someone like Friedman says this, you sit up and listen. The answer involves the 7th Ackermann function. The first Ackermann function is just doubling:
A_1(n) = 2n
The second Ackermann function of n is 2 to the nth power:
A_2(n) = 2^n
To calculate the third Ackermann function of n, you write down a tower of n 2's. For example
A_3(4) = 2^(2^(2^2))) = 65,536
And so on: to calculate the (k+1)st Ackermann function applied to n, you apply the kth Ackermann function n times to the number 1:
A_{k+1}(n) = A_k A_k ... A_k(1), where there are n A_k's.
For example A_4(4) is
2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(....
where the number of 2's in the tower is 65,536.
But this is still puny. Friedman showed that the longest word you can write down with three letters, following the rules I described, is finite in length but at least A_7(184) letters long.
As he notes, around A_5 "a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another."
If you have just one letter, this is the longest it can be:
AAA
If you have two, this is the longest it can be:
ABBBAAAAA
If you have three letters in your alphabet, there's still a finite upper bound on how long the word can be. But... it's incomprehensibly huge!
When someone like Friedman says this, you sit up and listen. The answer involves the 7th Ackermann function. The first Ackermann function is just doubling:
A_1(n) = 2n
The second Ackermann function of n is 2 to the nth power:
A_2(n) = 2^n
To calculate the third Ackermann function of n, you write down a tower of n 2's. For example
A_3(4) = 2^(2^(2^2))) = 65,536
And so on: to calculate the (k+1)st Ackermann function applied to n, you apply the kth Ackermann function n times to the number 1:
A_{k+1}(n) = A_k A_k ... A_k(1), where there are n A_k's.
For example A_4(4) is
2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(2^(....
where the number of 2's in the tower is 65,536.
But this is still puny. Friedman showed that the longest word you can write down with three letters, following the rules I described, is finite in length but at least A_7(184) letters long.
As he notes, around A_5 "a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another."
