「数学コラム 巨大有限数のお話(20) Uncomputableカテゴリの意味 （2019/08/31)」


前回のおさらい
　　ランク21 Uncomputableに属する巨大数は値を計算する事ができません。

Q.何故に計算出来ないのか？

A.無限ループの判定が出てくるから

例えば
　　BX関数(100) = 100文字で記述できるC言語コードを全て調べて、その中で最大の数を返す
　　
この関数の値は・・・・実は計算できません。(^_^A;

なぜなら、100文字のCコードと言うことは↓のコードを含みます。
(int は無限桁を保持できるものとする)
int i=1;
for(;;)
{
　　i*=2;
　　if (i%10==1)　　break;
}
return i;
ところがこれは無限ループであり、
プログラムが永遠に終わらないのでiを取り出すことができません。

つまりソースコードの中から
無限ループだけは
事前に取り除いておかなければならない。

しかし「無限ループの判定」と言うのは
恐ろしく難しい。


別のループの例を出すと

int i=1;
double x=0.5;
for(;;)
{
　　i*=2;
　　x = 3.9 * x* (1-x);
　　if (x < 0.1)　　break;
}
return i;

これはカオス関数の一例であり、
xは
0.5000
0.9500
0.1805
0.5620
0.9353
0.2297
0.6725
0.8368
0.5188
0.9486
0.1850
0.5731
...
のように激しく揺れ動く挙動を示し
xがどうなるのか非常～～～に読みづらい。

果たして
　　if (x < 0.1)　　break;
の条件は達成されるのか。
判定および証明はかなりの困難です。

少なくともコンピューター自身は黙々と計算してるだけで、自分が無限ループに入ってるのかわかってない。
だから人間がループの性質を研究し、手動で判定し、取り除いてやる必要がある。


いや、実際問題あらゆるソースコードを生成するということは

int i=1;

for(;;)
{
　　i= i*2;
　　if (XXX は素数か==true)　　break;
}
return i;

このような素数判定問題まで含めることができてしまう。

つまり無限ループの判定には「あらゆる数学的命題」についてYES/NOで答えられる
神の能力が解く必要になる。
それは不可能である。


一例としてBX関数を出しましたが、他のランク21 Uncomputableカテゴリ。
BB関数、Rayo数、ふぃっしゅ数なども
全部「n文字で記述できる全ての式を試し、その中で最大を探す」　　
総当り＆MAX方式を取ってます。

それらは全て
　　全ての式を生成　→　無限ループ問題を含む
事になるので、無限ループ判定問題が発生する。
だが無限ループの判定は"ほぼ"不可能である。

(完全に不可能ではない。
n文字で記述できる数学的問題を全て解き明かせば
　ループの無限/有限は判定できるので計算可能になるが、
　それはあまりにも難易度が高すぎて実質的には無理なのである)

よって

ランク21 Uncomputableに属する巨大数は値を計算する事ができません。
と、なります。