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

第29話 多変数関数同調グッドスタイン数列

　n変数関数遺伝的記法

　自然数aを底とする、(n個の自然数)→自然数 のn変数関数f(x_1,x_2,…,x_n )の「n変数関数遺伝的記法」とは、ある自然数mを次のように書き換えることである。

　ただしfは各項に関して、他の項が定数なら単調増加であるような関数であるとする。

　とaに関して、

　※

　f(a,0,0,…,0)≤mならば、

　f(0,0,…,x_n)≤m

　となるような最大のx_nを選び、sとする。

　次に、

　f(0,0,…x_(n-1),s_n )≤m

　となるような、最大のx_(n-1)を選び、s_(n-1)とする。

　以下同様に、s_1まで定める。ここで、

　m÷f(s_1,s_2,…s_(n-1),s_n )=t…m_1

　とする。

　このとき、f(a,0,0,…,0)≤m_1ならば

　f(s_1,s_2,…s_(n-1),s_n )+⋯(t個)… +m_1

　m_1<f(a,0,0,…,0)ならば、

　m_1÷a=p…q

　として、

　f(s_1,s_2,…s_(n-1),s_n )+⋯(t個)… +a+⋯(p個)… +q

　ここで、f(a,0,0,…,0)≤s_kであるようなkが存在する、または、f(a,0,0,…,0)≤m_1ならば、※からのmをs_kもしくは、m_1に読み替え、再度書き換える。

　注）式に現れる自然数が、すべてa以下になるまで書き換える。

　多変数関数同調グッドスタイン数列とは、

　初項が、「二つの自然数の数列A_mとN_mと、すべての自然数mに対して定義されたn変数関数f_mの組(A_1,N_1,f_1) 」であって、

　m項のNをA_m を底としたn変数関数遺伝的記法で書き、式に現れるA_mを全てA_(m+1)に書き換え、f_mをf_(m+1)に書き換えた値がN_(m+1)+1であり、m+1項は(A_(m+1),N_(m+1),f_(m+1))で表せるような組の列のことである。

　ここで、A_mはmに関する数列であり、Nとfにはよらない。

　具体的な巨大数の構成

　巨大数を実際に構成するには、数列A_m、初項N_1、多変数関数列f_mを定義すればよい。

　数列A_mは、大きさに影響をほとんど及ばさないので、

　A_m=m

　とする。

　f_mを構成するために、漸化的にG_(a,b) (n)と関連させながら定義する。

　任意のn変数関数同調グッドスタイン数列(m,N_m,f_m )とa,bに関して、

　G_(a,b) (0)=m

　1変数関数同調グッドスタイン数列(m,N_m,f_m)を

　f_1 (x)=x+1

　f_2 (x)=2x

　m≥3のとき、

　f_m (x)=x→2→(m-2)

　と定義し、N_1=nとしたときの項数をG_1,1 (n)とする。

　以下、k≥2のときG_(1,k) (n)を次のように漸化的に定義する。

　1変数関数同調グッドスタイン数列(m,N_m,f_m)を

　f_1 (x)=x+1

　m≥2のとき、

　f_m (x)=G^m_(1,k-1)(x)

　と定義し、N_1=nとしたときの項数をG_(1,k) (n)とする。

　上記の定義によりG^m_(1,k)(x)が定義された。ここで、n変数関数同調グッドスタイン数列(m,N_m,f_m)を

　f_1 (x_1,x_2…x_n )=x_n+1

　m≥2のとき、

　f_m (x_1,x_2,…x_(n-2),x_(n-1),0)=f_m (x_1,x_2,…x_(n-2),x_(n-1))

　f_m (x_1,x_2,…x_(n-1),x_n )=f_m (x_1,x_2,…G_(n-1,m) (x_(n-1) ),x_n-1)

　と定義し、N_1=nとしたときの項数をG_(n,k)(n)とする。

「これは、弱関数同調グッドスタイン数列と同じ構造ですね」

「ええ、その通りです。それが、多変数になっただけです。多変数遺伝的記法の複雑性は強関数グッドスタイン数列と同程度のはずです。しかし、その複雑性は、自身を参照しながら遥かに複雑になっていきます。少し例を見ながらやってみましょう」