自然數到底可以表示到多大?
版權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須註明原文網址 http://www.cnblogs.com/Colin-Cai/p/9683271.html 作者：窗戶 QQ/微信：6679072 E-mail：[email protected]
從很小我們 就知道，自然數有無限多個。
小朋友都對巨大的數有一種天然的憧憬，以至於很多人都會想過這麼一個問題，我們可以表示出多大的數？
小的時候，我就幻想著，我拿著一支筆，然後不斷的寫9，然後所寫的這個數就可以非常非常大了。長大一點才知道，這個根本不算什麼，隨便一個乘方就把它秒殺了。
以下我們來看看遞迴的神奇。
Ackermann函式
我想幾乎每個正統學習計算機的同學都見過Ackermann函式，
Ackermann函式帶兩個引數，兩個引數都是非負整數。
其定義如下：
對於Ackermann(m,n)，
(1) 如果m=0，則函式值為n+1
(2) 如果m>0且n=0,則函式值同Ackermann(m-1,1)
(3) 如果函式m>0且n>0，則函式值同Ackermann(m-1, Ackermann(m, n-1))
這個函式很恐怖，Ackermann(4,0)=13，Ackermann(4,1)=65533, Ackermann(4,2)有 19729 位，Ackermann(4,3)天知道……
運算子號的演化
我們最先學會的運算子號是加法，很快我就學會了相同的數連加。
8個2相加，寫起來如下
2+2+2+2+2+2+2+2
顯然，連加的寫法過於累贅，於是我們又學習了乘法，上述的式子可以寫成
2×8
於是頓時簡潔了很多。
注：根據不同理解，也有表示為8×2
自然而然，我們想到了連乘，它可以表達挺大的數了。
8個2相乘，寫起來如下
2×2×2×2×2×2×2×2
於是有了乘方來簡化，上述表示為2 8
有了乘方，終於有了第一個大殺器。我們可以連著寫乘方，以乘方的結果作為後面乘方的指數，如同連加、連乘那樣，比如
Line"/>
它運算的結合是從上往下結合，這個數是很誇張的大，這個宇宙不夠儲存它的十進位制下每一位。
高德納箭頭
提起高德納Knuth，應該計算機界的人都知道吧，我也不用多介紹了。
他以連加、連乘、連乘方為思路基礎，提出了高德納箭頭這樣的 運算子 。
a↑b = a b
a↑↑b = a↑a...↑a (一共有b個a)
a↑↑↑b = a↑↑a...↑↑a(一共有b個a)
...
a ↑ n b = a ↑ n-1 a ... ↑ n-1 a(一共b個a)
↑ n 我這裡表示為n個箭頭。
之前提到的
用高德納箭頭表示應該是2↑↑6
這個數箭頭只有2個，前後數字都很小，但是已經非常可怕的大了。
葛立恆數
這是曾經出現在數學證明中最大的自然數，不過後面被另外一個數學證明中的TREE(3)重新整理紀錄。這兩個數都與圖的染色有關，此處不深入。
葛立恆數是如下表示的：
g(0) = 4
g(1) = 3 ↑ g(0) 3
g(2) = 3 ↑ g(1) 3
...
g(64) = 3 ↑ g(63) 3
g(64)就是葛立恆數，這個數是誇張的大，別說數本身，就連它的箭頭的個數g(63)，人們也無法理解它的大小。
其實就連g(1)，人們已經無法理解其大小，甚至理解不了g(1)的大小的大小的大小的......大小。
Scheme來表示高德納箭頭
因為高德納箭頭的高階箭頭有個很簡單的往低階箭頭上展開的關係，所以用Scheme很容易表示，畢竟Lisp是很容易表示遞迴的。
(define (knuth n m cnt_arrow) (define (knuth-list lst cnt_arrow) (cond ((null? (cdr lst)) (car lst)) ((= 1 cnt_arrow) (knuth-list (cons (expt (cadr lst) (car lst)) (cddr lst)) 1)) (else (knuth-list (cons (knuth-list (make-list (car lst) (cadr lst)) (- cnt_arrow 1)) (cddr lst)) cnt_arrow)) ) ) (knuth-list (list m n) cnt_arrow) )
當然，上面只是表示出了其遞迴關係，在現有宇宙下計算不出來^_^比如之前那6個2我們肯定就算不出來，但是5個2也就是2↑↑5我們還是有希望的。
(knuth 2 5 2)計算結果就不貼了，是一個 19729 位的數，其實等於Ackermann(4,3)+3。
而之前葛立恆數雖然根本算不出來，但用Scheme表示還是很容易的。
(define Graham-Number (define (g n) (if (zero? n) 4 (knuth 3 3 (g (- n 1))) ) ) (g 64) )
康威鏈式箭頭
Conway，著名的生命遊戲的提出者，英國數學家。
他發明的康威鏈式箭頭是個比高德納箭頭還恐怖的東西。
所謂鏈式箭頭，是一串用箭頭串在一起的 正整數 ，比如
3->5
2->3->2
3->4->5->6
當然，只有一個數也算，那麼值就是數本身。鏈長至少為1。
另外，康威鏈式箭頭和高德納箭頭不一樣，高德納箭頭是運算子，康威鏈式箭頭只是用來連線一個序列。
康威鏈式箭頭怎麼計算呢？
它一共有5條規則，
(1) 如果鏈裡面只有一個數a，那麼值就是a本身
(2) 如果鏈裡面有兩個數，a->b，那麼值為a b
(3) 如果鏈長超過2，鍊形如X->a->1，其中X是一條鏈，那麼原鏈就等於X->a，也就是鏈長減1
(4) 如果鏈長超過2，鍊形如X->1->(a+1)，其中X是一條鏈，a是正整數（也就是最後一個數大於1，其實等於1也滿足，只是同時滿足兩條規則），原鏈值同鏈X
(5) 如果鏈長超過2，鍊形如X->(a+1)->(b+1)，其中X是一條鏈，a、b是正整數（也就是鏈尾的兩個數都大於1），原鏈值同X->(X->a->(b+1))->a
以上5條規則構造出了比高德納箭頭更瘋狂的東西。
瘋狂在哪裡呢？之前的葛立恆數g(64)已經很大了，可是以下不等式成立
3->3->64->2 < g(64) < 3->3->65->2
3->3->65->2 < 3->3->3->3
簡單的4個3， 秒天秒地
以上遞迴很明顯，很工整，用Scheme一樣表示，鏈式箭頭的序列就用Scheme裡的list直接就可以表示了：
(define (conway lst) (define (conway_rev lst) (cond ((null? (cdr lst)) (car lst)) ;規則1 ((null? (cddr lst)) (expt (cadr lst) (car lst))) ;規則2 ((= 1 (car lst)) (conway_rev (cdr lst))) ；規則3 ((= 1 (cadr lst)) (conway_rev (cddr lst))) ;規則4 (else (conway_rev (cons (- (car lst) 1) (cons (conway (cons (car lst) (cons (- (cadr lst) 1) (cddr lst)))) (cddr lst))))) ;規則5 ) ) (conway_rev (reverse lst)) )
於是，剛才秒天秒地的3->3->3->3就是(conway '(3 3 3 3))
