高德納箭頭表示法

本文簡介高德納箭頭表示法（Knuth’s up-arrow no­ta­tion），其為一種超運算的表示法，可用於表示大數。

高德納箭頭表示法

高德納箭頭表示法可以用來表示各種階數的超運算（hy­per­op­er­a­tion），可視為乘冪（ex­po­nen­ti­a­tion）的一種推廣。

定義

對於正整數 $k$ 與非負整數 $n \jcomma m \comma$我們定義 \[\begin{split}n \uparrow^k m = \begin{cases}1 & \when m = 0 \\[0.5ex] n^m & \when m \geq 1\ \text{且}\ k = 1 \\[1ex] n \uparrow^{k-1} (n \uparrow^k (m \varminus 1)) \hspace{-5em} & \\ & \when m \geq 1\ \text{且}\ k \geq 2 \end{cases} \period\end{split}\]

例子

範例 1　以下我們嘗試計算 $3 \uparrow^2 3 \period$依序計算可得：

• $3 \uparrow^2 0 = 1 \period$
• $3 \uparrow^2 1 = 3 \uparrow 1 = 3 \period$
• $3 \uparrow^2 2 = 3 \uparrow 3 = 27 \period$
• $3 \uparrow^2 3 = 3 \uparrow 27 = 7625597484987 \period$

因而 $3 \uparrow^2 3 = 7625597484987 \period$

範例 2　定義 $A_n = n \uparrow^n n \comma$其中 $n$ 為正整數。$A_n$ 被稱為第 $n$ 個阿克曼數（Ackermann number）。我們有：

• $A_1 = 1 \uparrow 1 = 1 \period$
• $A_2 = 2 \uparrow^2 2 = 2 \uparrow 2 = 4 \period$
• $A_3 = 3 \uparrow^3 3 = 3 \uparrow^2 (3 \uparrow^2 3) \semicolon$也就是說，\[\begin{split}\rod{2.5}{0}A_3 = 3 \uparrow^2 7625597484987 \period\end{split}\]用乘冪表示的話，會是由 7625597484987 個 3 堆成的乘冪塔。

參考資料

1. John H. Conway and Richard K. Guy. The book of numbers. Copernicus Publications, 1996.