テトレーション(tetration) は、ハイパー4演算子とも言われ [1] 、\(^yx = x^{x^{x^{.^{.^.}}}}\) (y個のx)で定義される2項演算である。すなわち、テトレーションは冪乗の繰り返しである。きちんと定義を書くと、
\[^0x=1\]
\[^{n + 1}x = x^{^nx}\]
となる。ここで、 \(n\) は非負整数である。
テトレーションは4番目のハイパー演算子で、ハイパー演算子の中では、はじめての本流の数学では使われない演算子である。テトレーションを繰り返すとペンテーションとなる。
\(c\)が小さくはない定数の時、関数 \(a(n) = {}^nc\) は急増加関数 \(f_3(n)\) と同じ速度で増加する。
Daniel Geisler は、この演算子のためにtetration.org というサイトを開設した[2]。
基本[]
- \[x \times y = \underbrace{x + x + \ldots + x + x}_y\]
- \[x^y = \underbrace{x \times x \times \ldots \times x \times x}_y\]
同様に、テトレーションは冪乗の繰り返しで定義される。
- \[^yx = \underbrace{x^{x^{x^{.^{.^.}}}}}_y\]
しかし、冪乗は交換法則が成り立たない演算子であるため(すなわち、\(a^{b^{c}}\)は一般的に\(\left(a^b\right)^c = a^{bc}\)と等しくない)、冪乗を下から上に向かって計算すると、テトレーションとは別の演算子ができ、Robert Munafoはこれをハイパー4演算子と呼んで、\(x_④y\)と書いている。\(x_④y\)は\(x^{x^{y - 1}}\)と書き換えることができるため、数学的には通常のテトレーションのような面白さが無い。
表記[]
テトレーションは色々な人が独立して考え、またあまり広く使われていないため、色々な表記法がある。
- \(^yx\) は "to-the-\(y\) \(x\)" あるいは "\(x\) tetrated to \(y\)." と読まれる。この表記法は Rudy Rucker によるものであり、これよりも上のハイパー演算子が使われないときに、最もよく使われる。
- Robert Munafo はハイパー4演算子 \(x^④y\)を使った。
- 矢印表記 では \(x \uparrow\uparrow y\) と書く。
- チェーン表記 では \(a \rightarrow b \rightarrow 2\) である。
- 配列表記 では \(\{x, y, 2\}\) あるいは \(x\ \{2\}\ y\)[3]である。
- ハイパーE表記 では E(x)1#y と書く。
- プラス表記では \(x ++++ y\) と書く。
- (Big Psi project で使われていた) スター表記では \(x *** y\) と書く。
- n個の2の冪乗の繰り返しは時折E*(n)と表記される。
- Harvey Friedman は \(x^{[y]}\) を使った。
性質[]
テトレーションは、冪乗までのハイパー演算子では存在していた対称的な性質の多くを失っているため、数学的な取り扱いが難しい。しかしながら、いくつかの性質を持っている。
指数の性質[]
\({^ba}^{^ca} = {^{c + 1}a}^{^{b - 1}a}\) が成り立つことを、以下のように簡単に示すことができる。
\[{^ba}^{^ca} = (a^{^{b - 1}a})^{(^ca)} = a^{^{b - 1}a \cdot {}^ca} = a^{^ca \cdot {}^{b - 1}a} = (a^{^ca})^{^{b - 1}a} = {^{c + 1}a}^{^{b - 1}a}\]
例えば、 \({^42}^{^22} = {^32}^{^32} = 2^{64}\) である。
上の位[]
\(^yx\) の最初の桁を現実的な時間で計算することは、おそらく不可能であろう。10進数では、このような式となる。
\[a^b = 10^{b \log_{10} a} = 10^{\text{frac}(b \log_{10} a) + \lfloor b \log_{10} a \rfloor} = 10^{\text{frac}(b \log_{10} a)} \times 10^{\lfloor b \log_{10} a \rfloor}\]
したがって、\(^ba\) の上位の桁は \(10^{\text{frac}(^{b - 1}a \log_{10} a)}\) となり、\(^{b - 1}a \log_{10} a\) の小数部分を計算する問題に帰着する。これは、任意の \(a\) 進数表記の \(^{b - 2}a\) を、\(^{b - 2}a\) 番目の桁から計算することと同じである。そのための、知られている最も効率の良いアルゴリズムは BBP algorithm であり、これは残念ながら線形時間を要するアルゴリズムで、しかも2の冪乗進数に対してのみ適用できる。\(^yx\) の最初の桁を現実的な時間で計算するためには、少なくとも \(O(\log^*n)\) (ここで \(\log^*n\) は iterated logarithm) の時間で計算できるアルゴリズムが必要となり、そのようなアルゴリズムが存在するとは考えにくい。
この障害は、さらに上のハイパー演算子においても続いている。仮に \(O(\log^*n)\) 時間のアルゴリズムが見つかったとしても、それはテトレーションの最初の桁を計算するのには役に立つが、ペンテーションの最初の桁を現実的な時間で計算することはできない。nに関わらず一定時間で計算できるアルゴリズムが必要となるが、そのようなアルゴリズムを見つけることは奇跡を期待するよりない。
一般化[]
\(y=-1 (x>0)\)[]
定義を拡張すると、
\(x↑↑0 = x↑(x↑↑(-1))\) より、
\(x↑(x↑↑(-1)) = 1\) となるので、
\(x↑↑(-1) = Log_{x} 1 = 0\) となる。
\(∴ x↑↑(-1) = 0 \)
\(x↑↑(-2)\)は定義できない
定義を拡張すると、
\(x↑↑(-1) = x↑(x↑↑(-2))\) より、
\(x↑(x↑↑(-2)) = 0\) となるが、
\(x↑↑(-2) = Log_{x} 0 → -∞\) となり、定義できない。
非整数 \(y\)[]
数学者の間で、非整数\(y\)に対する \(^yx\) 関数の定義については合意がされていない。実は、この問題はもっと一般的に、非整数\(t\)に対する \(f^t(x)\) の意味を考えることに帰着するのである。たとえば、 \(f(x) := x!\) としたときに、 \(f^{2.5}(x)\) はどんな関数になるだろうか?スティーブン・ウルフラムは、テトレーションの連続関数問題に非常に興味を持った。なぜならば、この問題は離散化されたシステムを「連続化」させるという一般的な問題を解くことにつながると考えたためである。
Geisler は、この問題をテイラー展開によって解こうとした[4]。関数 \(f \colon \mathbb{C} \to \mathbb{C}\) について、簡単のために \(f(0) = 0\) となるようにあらかじめ式変形をしておくと、このようにテイラー展開できる。
\[f(z) = \sum_{n = 1}^\infty \frac{f_n}{n!}z^n.\]
また、\(f_i\) を\(f\)の0における\(i\)次の導関数とし、さらに \(\lambda = f_1 = f'(0)\) とする。
まず、 \(f^t(z)\) の\(t\)に対する一次導関数を、合成関数の連鎖律を繰り返し適用することで計算する。
\begin{eqnarray*} Df^t(z) &=& Df(f^{t - 1}(z)) \\ &=& f'(f^{t - 1}(z))Df^{t - 1}(z) \\ &=& f'(f^{t - 1}(z))f'(f^{t - 2}(z))Df^{t - 3}(z) \\ &=& \prod_{i = 0}^{t - 1} f'(f^{t - i - 1}(z)). \\ \end{eqnarray*}
したがって、 \(f^t(z)\) の0における値は
\begin{eqnarray*} Df^t(0) &=& \prod_{i = 0}^{t - 1} f'(f^{t - i - 1}(0)) \\ &=& \prod_{i = 0}^{t - 1} f'(0) = f'(0)^t = \lambda^t. \\ \end{eqnarray*}
次に、 \(f^t(z)\) の二次導関数を計算する。
\begin{eqnarray*} D^2f^t(z) &=& D^2(f^t(z)) \\ &=& D(f'(f^{t - 1}(z))Df^{t - 1}(z)) \\ &=& D(f'(f^{t - 1}(z)))Df^{t - 1}(z) + f'(f^{t - 1}(z))D^2f^{t - 1}(z) \\ &=& f''(f^{t - 1}(z))(Df^{t - 1}(z))^2 + f'(f^{t - 1}(z))D^2f^{t - 1}(z). \\ \end{eqnarray*}
0における値はこのようになる。
\begin{eqnarray*} D^2f^t(0) &=& f''(f^{t - 1}(0))(Df^{t - 1}(0))^2 + f'(f^{t - 1}(0))D^2f^{t - 1}(0) \\ &=& f''(0)(Df^{t - 1}(0))^2 + f'(0)D^2f^{t - 1}(0) \\ &=& f_2(\lambda^{t - 1})^2 + \lambda D^2f^{t - 1}(0) \\ &=& f_2\lambda^{2t - 2} + \lambda D^2f^{t - 1}(0) \\ &=& f_2\lambda^{2t - 2} + \lambda f_2\lambda^{2t - 4} + \lambda D^2f^{t - 2}(0) \ (\lambda \neq 0) \\ &=& f_2\lambda^{2t - 2} + \lambda f_2\lambda^{2t - 4} + \lambda^2 f_2\lambda^{2t - 6} + \lambda D^2f^{t - 3}(0) \ (\lambda \neq 0) \\ &=& f_2 \sum_{i = 0}^{t - 1} \lambda^{2t - i - 2}. \\ \end{eqnarray*}
このような計算を続ければ、\(f^t(z)\)をテイラー展開した時の係数を順次計算できる。
\(y \rightarrow \infty\)[]
注目すべき関数に、次のように定義される無限テトレーションがある。
\[^\infty x = \lim_{n\rightarrow\infty}{}^nx\]
\(^\infty x\) が周期的に振動する(その逆は、無限に発散する)点を複素平面上にプロットすると、面白いフラクタル図形があらわれる。Daniel Geisler はその形を詳細に研究して、そのいくつかの特徴に対して名前をつけている。
例[]
いくつかのテトレーションの計算例を示す。
- \(^22 = 2^2 = 4\)
- \(^32 = 2^{2^2} = 2^4 = 16\)
- \(^23 = 3^3 = 27\)
- \(^33 = 3^{3^3} = 3^{27} =\) \(7625597484987\)
- \(^42 = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65536\)
- \(^35 = 5^{5^5} \approx 1.9110125979 \cdot 10^{2184}\)
- \(^52 \approx 2.00352993041 \cdot 10^{19728}\)
- \(^310 = 10^{10^{10}} = 10^{10000000000}\)
- \(^43 \approx 1.35 \cdot 10^{3638334640024} \approx 10^{10^{10^{1.11}}}\) = 第4548期の数
- \(^53 \approx 10^{6.46 \cdot 10^{3638334640023}} \approx 10^{10^{10^{10^{1.11}}}}\)
- \(^63 \approx 10^{10^{10^{10^{10^{1.1}}}}} \approx \) 宇宙論で使われた最大の数
負の数や非整数を使うと、無理数や複素数が出ることがある。
- \(^2{-2} = (-2)^{(-2)} = \frac{1}{(-2)^2} = \frac{1}{4}\)
- \(^3{-2} = (-2)^{(-2)^{(-2)}} = (-2)^{1/4} = \frac{1 + i}{\sqrt[4]{2}}\)
- \(^2(1/2) = (1/2)^{(1/2)} = \sqrt{1/2} = \frac{\sqrt2}{2}\)
- \(^3(1/2) = (1/2)^{(1/2)^{(1/2)}} = (1/2)^{\sqrt{2}/2}\)
擬似コード[]
下にテトレーションの擬似コードの例を示す。
function tetration(a, b): result := 1 repeat b times: result := a to the power of result return result
動画[]
- 巨大数動画シリーズ (ニコニコ動画) より
- 指数タワーを計算してみよう