たくさん進んで一歩下がる

第26話 強関数同調グッドスタイン数列

　さて、リディアさんは簡易なテーブルにマットを広げ、作ってきたお弁当を広げた。私の分までしっかりある。おにぎり、肉じゃが、きんぴらゴボウ、鮭の塩焼き、お新香、、なんというか、質素の代表格を並べると、豪華な和食になるんだな、と思う。結局食事の豪華さとは、どのような品目か、ではなく、どのように色と味と香りの色彩を調和させながら豊かにするか、ということなのだ。

　しばし巨大数から離れ、ここまでの道中、またはこれからの「音探しの丘」についての話が進む。食事も終わり、リディアさんがお茶を取り出すと、

「ところでグッドさん、お伝えしたもの・・・」

　と言ったので、下敷きと紙とペンを取り出した。

「音探しの丘を目の前にして申し訳ないですが、グッドさんもまだお話が終わっていないでしょう？

　音探しの丘では、話さずに歩くのがルールなんです。風がなければ500m離れた人の声も聞こえてしまいますからね」

「では、関数同調グッドスタイン数列の話、本題に入ります。

　単調増加関数fと自然数nの底をaとする関数遺伝的記法をまず例で示す。

　f=2nとし、1800を底を2の関数遺伝的記法で表そう。

　f^□(a)+□

　という形にするか、

　a+□

　という形にするのを繰り返す。

　f^9(2)+776

　さて、2より大きい数にこの操作を繰り返す。

　f^(f^3(2)+1)(2)+f^8(2)+264

　f^(f^(2+1)(2)+1)(2)+f^f^2(2)(2)+f^7(2)+8

　f^(f^(2+1)(2)+1)(2)+f^f^2(2)(2)+f^(f(2)+3)(2)+f^2(2)

　f^(f^(2+1)(2)+1)(2)+f^f^2(2)(2)+f^(f(2)+2+1)(2)+f^2(2)

　このような感じだ。これは弱関数同調グッドスタイン数列よりも高度な複雑性を作れていると思っていた。しかし、現実にはそれは誤りであった。この誤解は後で回収するとして、関数同調グッドスタイン数列を始めよう。ルールは弱関数同調グッドスタイン数列と全く同じである。nを与えてはじめ、G(n)を項数としよう。

　一応念のため確認しておくと、

　a世代目のf(n)は、

　a=1のとき

　f(n)=n+1

　a=2のとき

　f(n)=2n

　a≧3のとき

　f(n)=n→2→(a-2)

　それから、第一世代で、f(1)=f^1(1)という書き方ができてしまうが、^1は使わないことにする。

　n=1

　1

　1

　0

　G(1)=3

　n=2

　f(1)

　f(2)-1=3=2+1

　3

　3

　2

　1

　0

　G(2)=7

　n=3

　f^f(1)(1)

　f^f(2)(2)-1=31=f^(2+1)(2)+f^2(2)+f(2)+2+1

　f^(3+1)(3)+f^3(3)+f(3)+3

　f^(4+1)(4)+f^4(4)+f(4)+3

　f^(5+1)(5)+f^5(5)+f(5)+2

　f^(6+1)(6)+f^6(6)+f(6)+1

　f^(7+1)(7)+f^7(7)+f(7)

　f^(8+1)(8)+f^8(8)+8+8+...+8+7

　ここで、+8の項がすべて消えるためには、およそ8→2→6世代進める必要がある。

　その値をAとし、以降底は式の中でもaと書くことにすると

　a=Aのとき、

　f^(a+1)(a)+f^a(a)

　ここで、f^a(a)を崩すときに、

　その項を、弱関数遺伝的記法で書きでもしなければ、弱関数グッドスタイン数列と複雑性が変わらない、すなわち同じ強さになってしまうことに気付いた」

「グッドさんもいろいろ苦労なされたのね。たしかに私も弱関数同調グッドスタイン数列よりも一瞬強くなってるように見えました。これは少し考えなければいけないですね。弱関数同調グッドスタイン数列、関数同調グッドスタイン数列、そしてその先を考えたのですね？」

「実はアイディアの順序は逆で、弱グッドスタインを使わない関数同調グッドスタイン数列を思い付いたあと、弱グッドスタイン数列を思い付いたきましたが、それが同じ強さであることに気付きました。そこで、もともとの関数同調グッドスタイン数列を書き換えました。

　nとfのaを底とする強関数遺伝的記法とは、

　kはf(k)≧aかつf(k)≧5を満たす最大の自然数として

　①n≧f(a)のとき、

　n=f^s_1(a)^s_2×s_3+s_4

　の形に書き直す。s_1、s_2、s_3、s_4の順序でなるべく大きい自然数を選ぶ。

　②f(a)>n≧f(k)

　f(s_1)^s_2×s_3+s_4

　の形に書き直す。s_1、s_2、s_3、s_4の順序でなるべく大きい自然数を選ぶ。

　③f(k)>nのとき

　a^s_1×s_2+s_3

　の形に書き直す(遺伝的記法)。s_1、s_2、s_3の順序でなるべく大きい自然数を選ぶ。

　ただし、最後の項は0でもよい。

　さて具体例を与えよう。n=2000として、底を3、関数を2nとしよう。

　f(k)≧5を満たす、最大のkは3

　f^3(3)=24なので、n≧24のとき①が適用

　f(3)=6なので、24>n≧6のとき②が適用

　4>nのとき③が適用される。

　2000

　①を適用して

　f^9(3)+464

　9に②、464に①を適用して

　f^(f(4)+1)(3)+f^7(3)+80

　4に③、7に②、80に①を適用して

　f^(f(3+1)+1)(3)+f^(f(3)+1)(3)+f^4(3)+32

　32に①を適用して

　f^(f(3+1)+1)(3)+f^(f(3)+1)(3)+f^(3+1)(3)+f^3(3)+6

　6に②を適用して

　f^(f(3+1)+1)(3)+f^(f(3)+1)(3)+f^(f(2))(3)+f^3(3)+f(3)

　となる。

　そして、関数列を

　f_1(n)=n+1

　f_2(n)=2n

　f_a(n)=n→2→(a-2)

　とする。

　a≧3で、f(k)>aを満たすkは常に3であることに注意しよう。(そのために①でf(k)≧5という条件がある)

　強関数同調グッドスタイン数列とは

　与えられたnを底を1とする強関数遺伝的記法で書く。これを第1世代とする。

　a世代では、a-1世代の記法中に現れる底a-1を全てaに書き換え、1を引く。

　n=3から始めよう。

　f^f(2)(2)-1=31=f^(2+1)(2)+f^2(2)+f(2)+2+1

　f^(3+1)(3)+f^3(3)+f(3)+3

　f^(4+1)(4)+f^4(4)+f(4)+3

　f^(5+1)(5)+f^5(5)+f(5)+2

　f^(6+1)(6)+f^6(6)+f(6)+1

　f^(7+1)(7)+f^7(7)+f(7)

　f^(8+1)(8)+f^8(8)+f(7)^■×□+f(6)^■×□+... ...f(3)^■×□+8^■×7+7

　ここで、強関数遺伝的記法の強さがでている。大切なのは、f(3)のような項もこの先大きくなり続けるところだ。f_8(3)=3→2→8=3→3→7と十分巨大なことにも注意したい。

　そして、8^■×□のところは、グッドスタイン数列に対応するので、8^■×□の強さはε_0である。

　ここで、f(3)からの順序数との対応を見よう。

　f(3);ε_0+1

　f(3)×2;ε_0+2

　f(3)×a;ε_0+ω

　f(3)^2;ε_0+ω（×aより強いが近似できる）

　f(3)^a;ε_0+ω×ω

　f(4);ε_0+ω^3

　f(5);ε_0^ω^4

　f(a);ε_0^ω^ω

　※f(n+1)が、ε_0^ω^(n-1)+1であることがわかったので

　f(a+1);ε_0^ω^(ω+1)

　f(a×2);ε_0^ω^(ω×2)

　f(a^2);ε_0^ω^ω^2

　※fの中身はε_0^ω^■に対応することがわかった。

　f^2(3);ε_0^ε_0

　f^3(3);ε_0^(ε_0×2)

　f^a(3);ε_0^ε_0^2

　f^f(3)(3);ε_0^ε_0^ε_0

　ここは難しいところだが、合成回数f(3)自体の複雑性がε_0である。つまり、f^f(3)(3)以下の全ての式がε_0の複雑性で登場するため、ε_0^ε_0^(2+ε_0)=ε_0^ε_0^ε_0

　となる。

　f^f(4)(3);ε_0^ε_0^ε_0^ε_0

　f^f(a)(3);ε_1

　※ε_1=ε_0^ε_0^...

　f^f(a+1)(3);ε_1^ε_0

　f^f(a×2)(3);ε_1^ε_1

　f^f(a^a)(3);ε_2

　f^f^2(3)(3);ε_ω

　f^f^3(3)(3);ε_ε_ω

　f^f^a(3)(3);ζ_0=φ(2,0)

　f^f^f(3)(3)(3);ζ_ε_0=φ(2,ε_0)

　以下f^...f(■)(3)...(3)の■の複雑性が重層的にφ(k,□)の□に組み込まれる。

　よって、強関数同調グッドスタイン数列にnを与えた時の項数をGs(n)とすると、

　Gs(n)≒F_φ(ω,0)(n)

　となる」

「グッドさん・・・

　論理の細部はまだまだ不十分なところはあり、計算しないとわかりませんが、ζを超えたとするとそれは素晴らしいことですね」

「ええ、何度も迷い、何度も挑戦して作り込みましたからね。もう1時です。丘に行きましょうか」