求まるとは言ってない。
ふぃっしゅ数Ver1の定義を見てもなんじゃこりゃ？なんですが、
C++に落とし込むと大分わかりやすいかなと言う感じになった気がします。
間違っているかもしれないのでツッコミ待ちです。
ソース
# include <functional>
# include <iostream>
# include <tuple>
using namespace std;
typedef int Number;
typedef function<Number(Number)> BasicFunc;
typedef tuple<Number, BasicFunc> S_FuncParam;
typedef function<S_FuncParam(S_FuncParam)> SFunction;
typedef tuple<Number, BasicFunc, SFunction> SS_FuncParam;
Number Ack(Number a, Number b, BasicFunc f) {
if (a == 0) return f(b);
if (b == 0) return Ack(a - 1, 1, f);
return Ack(a - 1, Ack(a, b - 1, f), f);
}
Number G(Number x, BasicFunc f) {
return Ack(x, x, f);
}
S_FuncParam S(S_FuncParam param) {
Number n = get<0>(param);
BasicFunc f = get<1>(param);
return S_FuncParam(G(n, f), [=](Number x) {return G(x, f); });
}
SS_FuncParam SS(SS_FuncParam param) {
Number m = get<0>(param);
BasicFunc f = get<1>(param);
SFunction s = get<2>(param);
Number loop = f(m);
SFunction s2 = [=](S_FuncParam s) {
for (Number i = 0; i < loop; i++) s = S(s);
return s;
};
S_FuncParam ret = s2(S_FuncParam(m, f));
Number n = get<0>(ret);
BasicFunc g = get<1>(ret);
return SS_FuncParam(n, g, s2);
}
int main() {
SS_FuncParam ss(3, [](Number n) {return n + 1; }, S);
for (int i = 0; i < 63; i++) {
ss = SS(ss);
}
Number fish_number_1 = get<0>(ss);
Number fish_function_1 = get<1>(ss);
cout << fish_number_1 << endl;
}
型定義
typedef int Number;
typedef function<Number(Number)> BasicFunc;
typedef tuple<Number, BasicFunc> S_FuncParam;
typedef function<S_FuncParam(S_FuncParam)> SFunction;
typedef tuple<Number, BasicFunc, SFunction> SS_FuncParam;
Number 数値型です。本来は多倍長整数みたいな任意精度演算を指定するのですが、どうせ計算できないのでこだわる必要はないのかな？
BasicFunction Numberを引数にとってNumberを返す関数。a=f(x) の fです。
SFunction S変換の関数の型です。詳しくは後述。
S_FuncParam, SS_FuncParam S変換、SS変換の関数に渡すTupleです。
G関数
Number Ack(Number a, Number b, BasicFunc f) {
if (a == 0) return f(b);
if (b == 0) return Ack(a - 1, 1, f);
return Ack(a - 1, Ack(a, b - 1, f), f);
}
Number G(Number x, BasicFunc f) {
return Ack(x, x, f);
}
G関数は、(Number, BasicFunction)を引数にとってNumberを返す関数です。
中身はみんな大好きアッカーマン関数です。
要するに、数値を与えるとどでかい数値にしてくれる関数です。
本来のアッカーマン関数の初期値はb+1なんですが、そこがf(b)となっています。
最初こそf(n)=n+1ですから同じですが、このfという関数がドンドンパワーアップしていくので、最初からクライマックスです。やばい。
S変換
S_FuncParam S(S_FuncParam param) {
Number n = get<0>(param);
BasicFunc f = get<1>(param);
return S_FuncParam(G(n, f), [=](Number x) {return G(x, f); });
}
S変換は、(Number, BasicFunction)を引数にとって(Number, BasicFunction)を返す関数です。
中身は両方の値にG関数を通した形にします。
重要なのは、2つ目のBasicFuncもGを通す関数にする、って部分です。
S変換を通すたびに、関数そのものが育っていきます。
SS変換
SS_FuncParam SS(SS_FuncParam param) {
Number m = get<0>(param);
BasicFunc f = get<1>(param);
SFunction s = get<2>(param);
Number loop = f(m);
SFunction s2 = [=](S_FuncParam s) {
for (Number i = 0; i < loop; i++) s = S(s);
return s;
};
S_FuncParam ret = s2(S_FuncParam(m, f));
Number n = get<0>(ret);
BasicFunc g = get<1>(ret);
return SS_FuncParam(n, g, s2);
}
SS変換は(Number n, BasicFunction f, SFunction sfunc)を引数にとって(Number, BasicFunction, SFunction)を返す関数です。
中身は、f(n)回 sfuncを使います。
何度もsfuncを通す、って部分で数字を大きくするのですが、
返り値になっているSFunctionが「f(n)回 sfuncを通す」に変わっているのがポイントです。
main
int main() {
SS_FuncParam ss(3, [](Number n) {return n + 1; }, S);
for (int i = 0; i < 63; i++) {
ss = SS(ss);
}
Number fish_number_1 = get<0>(ss);
Number fish_function_1 = get<1>(ss);
cout << fish_number_1 << endl;
}
先程のSS変換に初期値(3, n => n + 1, S)を63回通せば、最初の値がふぃっしゅ数Ver1になります。
で、2個めの関数の事をふぃっしゅ関数Ver1と呼びます。
全体解説
SS変換はSFunctionを育てて、SFunctionはBasicFunctionを育てます。
つまり数を大きくすると同時に、数を大きくする関数そのものも育てているのがS変換、SS変換の肝となります。
序盤だけみてみましょう。
まず、f(x)=x+1ですので、f(3)=4となります。
ですから、最初のSS変換はS変換を4回行います。
G(f(x)) の事をGf と書き表すと、4回のS変換は以下のようになります。
(3,f)→(G(3),Gf)→(G'Gf(3), G'Gf)→(G''G'Gf(3), G''G'Gf)→(G'''G''G'Gf(3), G'''G''G'Gf)
Gにダッシュがついています。
G関数は(Number, BasicFunction)を引数とるものですので、
最初のG関数の初期値(a=0のときの値)はf(b)です。
しかし、2回目のG'関数の初期値はGf(b)と最初に比べて強くなっています。
G''関数は初期値をG'Gf(b)となった、さらに強くなった関数です。
SS変換1回めが終わりこのようになりました。
(3, f, S)→(G'''G''G'Gf(3), G'''G''G'Gf, (G'''G''G'Gf(3), G'''G''G'Gf))
SS変換2回目いってみましょう。
2回目はG'''G''G'Gf(3)回、S'変換を行います。
すでに計算できませんし、実際グラハム数を超えます。(はず)
ということで、63回もこれをやるととんでもない大きい数だと思います。