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

第25話 弱関数同調グッドスタイン数列

　そして、森を歩き続ける。なかなかハードだ。たまに手を使わなければ登れないような石を乗り越えていったり、吊橋を渡ったり。でも以外と楽しいものだ。

　リディアさんはヒョイヒョイ越えていく。私はなんとか追いついていくが、私に一応スピードを合わせてくれているようだ。私のスピードがωならω+1くらいのスピードだ。

　私がそうやってついていきながらも、リディアさんは虫と戯れたり、小動物を見つけてみたり、木の枝にぶら下がってみたり、と楽しそうだ。こんなに野生的な人だったんだな。

「それで、関数同調グッドスタイン数列のお話、聞かせて下さる？」

「ええ、まず、今までの結論からいうと、遺伝的記法が複雑化するほどよく、演算の種類は、特に影響を及ぼさないということだった。しかし、無限に演算を用意すればどうか？これこそが、関数同調グッドスタイン数列のアイデアの出発点だ。まず、弱関数同調グッドスタイン数列の説明をしよう。計算が楽で、後に使う、関数同調グッドスタイン数列の計算の助けになる。

　使う演算は、

　f_a

　+

　の2つ。ただし、aはその時の底だ。

　そして、今回は底が1から始まる。

　しかしその前にまず、弱関数遺伝的記法を定義しよう。

　ある単調増加関数fと自然数nのaを底とした関数遺伝的記法とは。まず具体例から。

　f(n)=2nとして、底を3とし、自然数を85としよう。まず、

　85=f(□)×k + □

　という形にしたい。kは、k項の足し算の省略で、底とは関係ない。

　fのほうの□に入る最大の数は42だ。では、それを使って書き直そう。

　85=f(42)+1

　そして、3以上の数をどんどん書き直していく

　=f(f(21))+1

　=f(f(f(10)+1))+1

　=f(f(f(f(5))+1))+1

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

　ここで、f(5)=f(3+2)と書き直したところが重要で、もしf(f(2)+1)としてしまうと、グッドスタイン数列を構成できない。

　まとめるとこうだ。

　関数f(x)と、自然数nの、aを底とした関数遺伝的記法とは、

　f(a)≧nのとき、

　n=f(s)×k+t

　ただし、sはf(s)≦nとなるような最大の自然数

　kはf(s)×k≦nとなるような最大の自然数

　t=n-f(s)×k

　f(a)<nのとき、

　n=a×l+u

　ただし、lはa×l≦nとなるような最大の自然数

　とする。書き換えた後の式のsとtをさらに遺伝的記法で書き換え、登場する全ての自然数がa以下になるまで続ける。

　と定義する。そして、弱関数同調グッドスタイン数列は、底がaのとき、関数自体もf_aになる。

　この関数は簡単にこうきめよう。

　f_1(n)=n+1

　f_2(n)=2n

　f_3(n)=n^2

　a≧3のとき、

　f_a(n)=n^^...a-2個...^2

　ポイントは、a=1のときの弱さにある。これがこの弱関数同調グッドスタイン数列を魅力的にしてくれている。

　そして、いよいよ弱関数同調グッドスタイン数列だ。

　①関数f_1と自然数nの底が1である弱関数遺伝的記法で書く

　②記法中の1を全て2に置き換えた(f_1もf_2になる)値から1を引く

　①'関数f_2とその値の底が2である弱関数遺伝的記法で書く

　②'記法中の2を全て3に置き換えた値から1を引く

　以降は、

　①"関数f_aとその値の底がaである弱関数遺伝的記法で書く

　②記法中のaを全てa+1に置き換えた値から1を引く

　を繰り返していく。

　いくつか小さい数から始めて様子を見よう。nから始めた弱関数同調グッドスタイン数列の項数をG(n)で表す。そして、f_aは、fと省略する。

　n=1

　a=1;1

　a=2;1

　a=3;0

　G(1)=3

　n=2

　a=1;f(1)

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

　a=3;3

　a=4;3

　a=5;2

　a=6;1

　a=7;0

　G(2)=7

　n=3

　a=1;f(f(1))

　a=2;f(f(2))-1=7=f(2+1)+1

　a=3;f(3+1)

　a=4;f(4+1)-1=3124=f(4)×12+4×13+1

　a=5;f(5)×12+5×13

　a=11;f(11)×12+5×12

　a=49151;f(49151)×12

　a=49152;f(49152)×11+49152×A+t

　ここでAはおよそ49152→2→49150≒3→3→50000

　で、tは49151以下の自然数

　49152×Aが消えるまでの操作はほとんど無視できる。そのときのa=A'とする。(A≒A')

　a=A';f(A')×11

　a=A'+1;f(A'+1)×10+(A'+1)×B

　ここでBはおよそ、

　3→3→A≒3→3→(3→3→50000)≒3→3→2→2

　結局f(a)が一つ減るのは4変数チェーンの右から二番目を一つ増やすに相当する。よって、

　G(3)≒3→3→12→2≒F_ω+1(12)

　ここでFは急増加関数

　n=4

　a=1;f(f(f(1)))

　a=2;f(f(f(2)))-1=15=f(7)+1=f(f(2+1)+1)+1

　a=3;f(f(3+1)+1)

　a=4;f(f(4+1)+1)-1=3126^3126-1=f(f(4+1))×8494+4×A+t

　ここで、(x+1)^^2/x^^2≒(x+0.5)e、(eは自然対数の底)を使用

　ここで、A'≒3126^3126≒5^^5とする。

　a=A;f(f(A+1))×8494

　ここから先はすこし具体的に計算するのが難しい。

　a=3のときの形をもう一回見よう。

　f(f(a+1)+1)

　さて、a=4以上のときの一番左の項は、次の様な変化をたどる。mは小さな自然数

　f(f(a+1)+1)

　f(f(a+1))

　f(f(a)+f(a)+...+m)

　...

　f(f(a)+1)

　f(f(a))

　f(a+a+...+m)

　...

　f(a+a+1)

　f(a+a)

　...

　f(a+2)

　f(a+1)

　f(a)

　f(a)が消えるのは、急増加関数の順序数において、+1に相当するのだった。以下、対応をしめす。

　f(a);1

　※f(a+1)はf(a)の項がたくさんできる、すなわち+1をたくさんするので、

　f(a+1);ω

　※f(a+1+1)と見ると、+ωに相当するf(a+1)がたくさんできるので、

　f(a+2);ω×ω

　※f(α+1)というのは、f(α)に相当する順序数に×ωをすることがわかった。これをたくさん繰り返すので、

　f(a+a);ω^ω

　f(a+a+1);ω^ω×ω

　f(a+a+a);ω^ω×ω^ω

　※f(α+a)は、f(α)に相当する順序数に×ω^ωをすることがわかった。これをたくさん繰り返すので、

　f(f(a));(ω^ω)^ω=ω^(ω×ω)

　※f(α+f(a))は、f(α)に相当する順序数に×ω^(ω×ω)をすることがわかった。以下少し確認しながら見ていく。

　f(f(a)+1);ω^(ω×ω)×ω=ω^(ω×ω+1)

　f(f(a)+a);ω^(ω×ω)×ω^ω=ω^(ω×ω+ω)

　f(f(a)+a+a);ω^(ω×ω+ω×2)

　f(f(a)+f(a));ω^(ω×ω×2)

　f(f(a+1));ω^(ω^3)=ω^ω^3

　f(f(a+1)+1);ω^ω^3×ω=ω^(ω^3+1)

　これで、解析終了だ。

　よって、n=4のときは、

　G(4)≒F_ω^(ω^3+1)

　と近似できる。急増加関数の変数が書かれていないが、何を入れても大して変わらない。

　G(5)は、f(f(f(a+1)+1)+1)を解析すればよい。ここまま解析を続けると

　f(f(a+1)+f(a));ω^ω^3×ω^(ω×ω)

　f(f(a+1)+f(a+1));ω^ω^3×ω^ω^3

　※よって、f(α+f(a+1))は、×ω^ω^3に相当することがわかる。

　f(f(a+2));(ω^ω^3)^ω=ω^ω^4

　f(f(a+a));ω^ω^ω

　※f(α+f(a+a))は、+ω^ω^ωに相当

　f(f(a+a+1));(ω^ω^ω)^2=ω^(ω^ω×2)

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

　※f(f(α+a))は、ω^(ω^(ω+□))の□に+1相当

　f(f(f(a)));ω^ω^(ω×ω)

　f(f(f(a+1)));ω^ω^(ω×ω×ω)

　f(f(f(a+1)+1)+1);ω^(ω^ω^3×2+1)

　これが、G(5)の評価である。もう少しだけ解析を続けよう。

　f(f(f(a+a)));ω^ω^ω^ω

　これで、規則性が見えた。

　f(a+a);ω^ω

　f(f(a+a));ω^ω^ω

　f(f(f(a+a)));ω^ω^ω^ω

　f^k(a+a);ω^^k

　美しい関係だ。

　さて、ここで大雑把に近似すると、

　G(n)≒F_ω^^n(n)

　すなわち

　G(n)≒F_ε_0(n)

　だ。実際には、普通のグッドスタイン数列も

　G(2^^n)≒F_ε_0(n-1)

　なので、効率化がされたとはいえ、本質的に強くなった、とは言い辛いね」

「でもとても面白いですね。少しでもグッドスタイン数列を拡張できているというのは素晴らしいと思います。でもおそらくグッドさんはもっと先を見ているのでしょう？そのお話を一刻も早く聞きたいけれども、ついに音探しの丘に到着ですよ。お昼を頂いてから、歩きにいきましょうか」

　話すのに夢中になっていたのか、リディアさんの癒やしの効果か、殆ど疲れずに丘に到着していたようだ。