ふぃっしゅ数ver.1のS変換について

ふぃっしゅ数ver.1の定義に出てくるS変換の定義と、大きさについて述べます。証明はガッツリ省略していきます。

ふぃっしゅ数ver.1は、$3$という小さい自然数と、$f(x) = x+1$という単純な関数の組$(3,f)$に対して、$S$変換を膨大な回数繰り返すことで定義されます。

この記事では、組$(3,f)$に対して$S$変換を1,2回繰り返したものの大きさについて説明します。

なお、ここでは$S$変換を$k$回繰り返した組の自然数側を$m_k$とし、関数側を$f_k$とします。
特に、$m_0 = 3,\ f_0(x) = x+1$となります。$m_1,f_1,m_2,f_2$は今から説明します。

$S$変換$1$回目

具体的な入力$(m_0,f_0)$に対して、$S(m_0,f_0)$を計算してみます。

さて、この定義中に出てくる2変数関数$B$は、『アッカーマン関数』として有名な関数です。
特に、

• $B(0,n) = n+1$
• $B(1,n) = n+2$
• $B(2,n) = 2n+3$
• $m > 2$のとき、$B(m,n) = 2\uparrow^{m-2}(n+3)-3$

が成り立ちます。
なので、$g(0) = B(0,0) = 1,\ g(1) = B(1,1) = 3,\ g(2) = B(2,2) = 7$であり、
$x > 2$のとき$g(x) := B(x,x) = 2\uparrow^{x-2}(x+3)-3$となります。

$g(3) = 2\uparrow^{3-2}(3+3)-3 = 2\uparrow 6 - 3 = 2^6 -3 = 61$です。
よって、$S(m_0,f_0) = (61,g)$となります。

さて、改めてこの組を$(m_1,f_1)$と呼ぶことにします。
記号として置いているだけで、$m_1 = 61$ですし、$x > 2$のとき$f_1(x) = 2\uparrow^{x-2}(x+3)-3$を満たす関数です。

次は$S(m_1,f_1)$を計算していきます。

$S$変換$2$回目

具体的な入力$(m_1,f_1)$に対して、$S(m_1,f_1)$を計算してみます。

ここで出てくる$B,g$は、先ほどの$S(m_0,f_0)$の定義に出てくる$B,g$とは別物であることに注意しましょう。

$B(0,n)$

$B(0,n) = f_1(n)$なので、$B(0,0) = 1,\ B(0,1) = 3,\ B(0,2) = 7$です。
$n > 2$のときは$B(0,n) = 2\uparrow^{n-2}(n+3)-3$なのですが、この時点で十分大きいですね。
$B(0,3) = 61$ですし、$B(0,4) = 2\uparrow\uparrow 7 -3 = 2^{2^{2^{2^{2^{2^2}}}}}-3 = 2^{2^{2^{65536}}}-3$です。この時点でグーゴルプレックスどころかグーゴルプレックスプレックスより大きいです。

厳密な等式だと$B(0,n) = 2\uparrow^{n-2}(n+3)-3$のように微妙に長いのでもう少しざっくり書くと、$B(0,n) \ge 3\uparrow^{n-2}3 +2$となります。
(ぶっちゃけ最後の$+2$はグラハム数と比較するときにしか使わないので、$B(0,n) \ge 3\uparrow^{n-2}3$で十分です。)

$B(1,n)$

計算ルールに基づいて、$B(1,n)$を計算すると、
$B(1,n)$
$= B(0,B(1,n-1))$
$= B(0,B(0,B(1,n-2)))$
$= \cdots$
$= \underbrace{B(0,B(0,\cdots,B(0,}_{B(0,\cdots)\textrm が n\textrm 個}B(1,0))\cdots))$
$= \underbrace{B(0,B(0,\cdots,B(0,}_{B(0,\cdots)\textrm が n\textrm 個}B(0,1))\cdots))$
$= \underbrace{B(0,B(0,\cdots,B(0,B(0,}_{B(0,\cdots)\textrm が n+1\textrm 個}1))\cdots))$
となります。

勘のいい方はお気づきかもしれませんが、これヤバすぎです。

具体的に$n$に色々入れて計算してみると、
$B(1,0) = B(0,1) = 3$
$B(1,1) = B(0,B(0,1)) = B(0,3) = 61$
$B(1,2) = B(0,B(0,B(0,1))) = B(0,B(0,3)) = B(0,61) = 2\uparrow^{59}64 -3$
と、この時点で非常に大きいです。
右っ側の数を1つ増やすと、さっきの計算結果からほんの少し減らしたものが今度は矢印の本数になってしまうのです。

ここで、さっきの$B(0,n) \ge 3\uparrow^{n-2}3 +2$を使うとグラハム数との比較ができます。
$B(1,1) = 61$なので、
$B(1,2) = B(0,B(1,1)) = B(0,61) \ge 3\uparrow^{59}3 +2$
$B(1,3) = B(0,B(1,2)) \ge B(0,3\uparrow^{59}3 +2) \ge 3\uparrow^{3\uparrow^{59}3 +2-2}3 +2 = 3\uparrow^{3\uparrow^{59}3}3 +2$
$B(1,4) = B(0,B(1,3)) \ge B(0,3\uparrow^{3\uparrow^{59}3}3 +2) \ge 3\uparrow^{3\uparrow^{3\uparrow^{59}3}3 +2-2}3 +2 = 3\uparrow^{3\uparrow^{3\uparrow^{59}3}3}3 +2$
...

$B(1,65)$
$\ge 3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{\cdots^{3\uparrow^{59}3}\cdots}3}3}3}3}3\ \Bigg\}{3\uparrow^\cdots3 } \textrm が 64\textrm 個$
$\ge 3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{\cdots^{3\uparrow^43}\cdots}3}3}3}3}3\ \Bigg\}{3\uparrow^\cdots3 } \textrm が 64\textrm 個 = \textrm{グラハム数}$

のようになります。グラハム数越えちゃいましたね。あっさりと。

$B(2,n)$

計算ルールに基づいて、$B(2,n)$を計算すると、
$B(2,n)$
$= B(1,B(2,n-1))$
$= B(1,B(1,B(2,n-2)))$
$= \cdots$
$= \underbrace{B(1,B(1,\cdots,B(1,}_{B(1,\cdots)\textrm が n\textrm 個}B(2,0))\cdots))$
$= \underbrace{B(1,B(1,\cdots,B(1,}_{B(1,\cdots)\textrm が n\textrm 個}B(1,1))\cdots))$
$= \underbrace{B(1,B(1,\cdots,B(1,B(1,}_{B(1,\cdots)\textrm が n+1\textrm 個}1))\cdots))$
となります。

これもヤバすぎです。

具体的に$n$に色々入れて計算してみると、
$B(2,0) = B(1,1) = 61$
$B(2,1) = B(1,B(1,1)) = B(1,61) \ge 3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{\cdots^{3\uparrow^{59}3}\cdots}3}3}3}3}3\ \Bigg\}{3\uparrow^\cdots3 } \textrm が 60\textrm 個$
と、この時点でグラハム数レベルの巨大数となります。
$B(2,2) = B(1,B(2,1)) \ge 3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{\cdots^{3\uparrow^{59}3}\cdots}3}3}3}3}3\ \Bigg\}{3\uparrow^\cdots3 } \textrm が B(2,1)-1\textrm 個$
グラハム数は階層で$64$個だったのに対し、$B(2,2)$は$B(2,1)-1$個なので、こっちの方が圧倒的にデカいんですね。
特に、$g(2) = B(2,2)$なので、$g(2)$の時点でグラハム数越えです。

この後も繰り返していくと、
$B(2,n+1) = B(1,B(2,n)) \ge 3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{3\uparrow^{\cdots^{3\uparrow^{59}3}\cdots}3}3}3}3}3\ \Bigg\}{3\uparrow^\cdots3 } \textrm が B(2,n)-1\textrm 個$
となります。
グラハム数が$64$段である部分に$60$を入れたものが$B(2,1)$で、$B(2,1)$を入れたものが$B(2,2)$で、$B(2,2)$を入れたものが$B(2,3)$で、...のような構造になってるので、グラハム数とは比較にならないほど大きな数がこの段階で量産されます。

$B(3,n)$

先ほどと同様に$B(3,n)$を計算すると、
$B(3,n) = \underbrace{B(2,B(2,\cdots,B(2,B(2,}_{B(2,\cdots)\textrm が n+1\textrm 個}1))\cdots))$
となります。

先ほど$B(2,n)$の大きさを説明したのですが、今度はその$B(2,n)$を繰り返します。案の定ヤバすぎです。
特に、$g(3) = B(3,3) = B(2,B(2,B(2,B(2,1)))) = B(2,B(2,B(2,\textrm{グラハム数より少し小さい})))$
となります。
$B(2,2)$がグラハム数より圧倒的に大きいのですが、それを何度も重ねます。

$B(m+1,n)$

同様に、
$B(m+1,n) = \underbrace{B(m,B(m,\cdots,B(m,B(m,}_{B(m,\cdots)\textrm が n+1\textrm 個}1))\cdots))$
となります。

矢印表記は、$\uparrow$を繰り返す$\uparrow\uparrow$を繰り返す$\uparrow\uparrow\uparrow$を繰り返す...という流れになってますが、
$B$も同様に、$B(0,\cdots)$を繰り返す$B(1,\cdots)$を繰り返す$B(2,\cdots)$を繰り返す...という流れでどんどん大きな数を生み出せるようになります。
この段階を$61$階繰り返した$B(61,\cdots)$を使った数が、$g(m_1) = g(61) = B(61,61)$です。
また、$g$はこの$B$の左変数を弄れる関数なので、今までの関数達が全て無に帰すレベルの関数です。

ということで、$S(m_1,f_1) = (g(m_1),f_1)$は、とんでもなく大きい数と、とんでもなく大きい数をいとも容易く作る関数の組になります。

$S$変換$2$回目でこれです。

結局$S$変換って何してんの？

$S$変換は、「自然数と関数の組」を、「とんでもなく大きい数と、大きい数を作る関数の組」に変換します。
ですが、実のところ$S$変換の強みは関数の強化の部分で、最終的に関数が強化されれば自然数の方はあまり気にしなくてよかったりします。
ということで、$S$変換がどう関数を強化してるかを見ていきましょう。

関数$f$を$S$変換したものを定義する最中に出てくる2変数関数$B$は、
$B(0,n) := f(n)$
$B(m+1,0) := B(m,1)$
$B(m+1,n+1) := B(m,B(m+1,n))$
のように定義されます。

ですが、先ほどの議論を使えば、
$B(0,n) := f(n)$
$B(m+1,n) := \underbrace{B(m,B(m,\cdots,B(m,B(m,}_{B(m,\cdots)\textrm が n+1\textrm 個}1))\cdots))$
のように書き換えられることがわかります。
この形で見ると、$B(1,\cdots)$が$B(0,\cdots)$(つまり$f$)を繰り返す関数であり、$B(2,\cdots)$が$B(1,\cdots)$を繰り返す関数であり、$B(3,\cdots)$が$B(2,\cdots)$を繰り返す関数であり、...となっていることがわかります。
このように、$B(m,n)$は$f$を繰り返した関数を繰り返した関数を繰り返した関数を...という関数達を全て集めたものになります。

関数の繰り返しというのは、かけ算を指数に、指数をテトレーションに、矢印表記をグラハム数にするように、関数をとんでもなく強化する手法です。それを一度だけではなく実質何回でも行えるので、$S$変換は非常に優れた関数の強化方法なのです。