東方巨大数2「藍数」

■ 藍数
-------------------------

■ 定義

自然数mと、十分大きな自然数nについて、集合Rと関数Sを次のように定義する。

R(0,n)=n状態以下の2記号チューリングマシンの集合
R(m,n)=R(0,n) ∪ R(1,n) ∪ ... ∪ R(m-1,n) の停止問題を判定できるオラクルを備えた、S(m-1,n)状態以下の2記号チューリングマシンの集合
S(m,n)=R(m,n)の要素でかつ停止するチューリングマシンが停止までにシフトする数の最大値(以下、最大シフト数と呼ぶ)
    ※最大シフト数S(m,n)は、シェン・リンの最大シフト数関数をR(m,n)に対して適用したものである

このときグラハム数Gについて、S(G,G) の計算結果である自然数を『藍数』とする。


■ 計算過程とその考察

R(0,n)は、nが有限の自然数であるならば全ての2記号チューリングマシンを列挙すればよく、有限集合となる。
S(0,n)は、R(0,n)についての最大シフト数を求めるにあたり、チューリングマシンの停止問題を解く必要があるため、計算不能な数である。

ここで、R(0,n)の停止問題を解くことのできるオラクルを備えた、以下の計算を行うチューリングマシンY[0]を用意する。

    1: R(0,n)の全要素について停止問題をオラクルに解かせる
    2: 停止すると判定されたチューリングマシンをエミュレートし、シフト回数をカウントする
    3: 停止するチューリングマシン全てのシフト回数のうち、最大の値を「最大シフト数」として出力する

チューリングマシンY[0]は、有限集合R(0,n)の要素の中でも停止するマシンのみをエミュレートするため、有限時間内に計算を完了することができる。
これによってS(0,n)の値を計算することが可能となる。
R(1,n)の構成に必要なS(0,n)が求められたため、R(1,n)を有限集合として構成することが可能となる。

なおチューリングマシンY[0]もR(1,n)の要素である。
(そのために n は万能チューリングマシンを定義可能な大きさを持っている必要がある)

以下、同様に
    R(1,n)を作成 → Y[1]を用意してS(1,n)を計算 →
    R(2,n)を作成 → Y[2]を用意してS(2,n)を計算 → ... →
    R(m,n)を作成 → Y[m]を用意してS(m,n)を計算
という手順をたどることで、

オラクル有りの条件下において、自然数mと、十分大きな自然数nについて、
S(m,n) を計算して有限時間内に停止するアルゴリズムを構成可能である。


■ その他の考察

・矛盾の発生可能性について
    S(x,y)を計算するY[x]は、自分自身を入力とすることはない。そのため矛盾は発生しない。

・Sの増加スピードについて
    増加の下限値
        Y[x] は R(x,n) のうち停止するものについてエミュレートを行うため、Y[x]のシフト数の下限はR(x,n)のシフト数の総和に等しい。
        Y[x] は R(x+1,n) に含まれるため、S(x+1,n) - S(x,n) の下限値は R(x,n) のシフト数の総和となる。
    実際のところは
        状態数が最大シフト数関数 S に沿って増加するため、前述の下限値よりも明らかに大きな速度で増加していくはずである。

・n の最小値について
    実際に万能チューリングマシンを構成可能な状態数以上であればよいため、大きく見積もっても天文学的数字で十分である。

・計算可能性について
    S(m,n) の値は計算不能であるが、それより一段上の算術的階層に位置する Y[m] にとっては計算可能である。
    『計算可能と計算不能の境界』を行き来しながら有限時間内に停止するアルゴリズムを示した、という点では計算可能と考えている。

・実際の『藍数 S(G,G)』の大きさについて
    S(G,G) すなわち『藍さま』を計算できる Y[G] すなわち『紫さま』が自分の近くにはいないので、自分には想像もできません。

以上.