「数学コラム 巨大有限数のお話13 最強のBX関数 (2) （2019/03/13)」


数学コラム 巨大有限数のお話13 最強のBX関数 (2)


おさらい。
巨大数ランク表：

ランクカテゴリ名スケール相撲スケール
0特になし10一般人
.........
19Higher computablefθ(x)優勝
20Unreadable不明人間じゃない
21Uncomputable計算不可能。生物じゃない

BX関数は
「n文字で記述できる全てのCソースコードを生成し、その中で最大を調べる。」

ランク21に君臨する最大の巨大有限数です。

これまでに紹介した有限巨大数、
TREE(3)＝ランク18、SCG(13)＝ランク19、,Loader数＝ランク20
などは全てCソースコードで記述できますので
BX関数はそれらを含め、上回ります。

「記述可能」であればあらゆる巨大数はBX関数に含まれます。



まさに無敵。完全にチート的なBX関数なんですが・・・^^;
BX関数には重要な欠点があり
実はBX関数の値を計算する事はできません！





解説：
なぜならCソースコードの中には

無限.c

　　for (int i=0;i!=-1;i++)　　{;}


のような無限ループを含み、永遠に出力が出てこないパターンもあるからです。
そう。これがあった。無限ループ！

しかもBX関数は
「n文字で記述できる全てのCソースコードを生成し、その中で最大を調べる。」

自身の定義により無限ループを含むソースコードを生成してしまいます。

無限ループに入るとプログラムが終わらないので
これらだけはBX関数から除外する必要がある。



・・・・が！
先程のケースでは演習のためにループ抜けの条件をわかりやすくしましたが、


無限2.c

　　int i=1;
　　for (;;)
　　{
　　　　i = i*2;
　　　　if (i%10 == 3)　　break;
　　}



このようにループを抜ける条件が複雑になると
そのループは果たして無限ループなのか、
いつかは終わる有限ループなのか判定が非常に難しくなる。
さらにもっと難しい条件になれば判定の難易度はどんどん高くなる。

全てのループに通用する無限/有限の判定方法は
存在しない事がチューリングの定理によって証明されています。



つまり～
　・BX関数は全てのCソースコードを生成。
　・全てのCソースコードを生成すると、無限ループを含んでしまう。
　・無限ループは計算が終わらないのでBX関数の中から除去する必要がある
　・全てのループに通用する、ループ判定アルゴリズムは存在しない事が証明されている。
　・無限ループの判定/除去はできない
　→　BX関数は計算ができない。



う～ん。深い・・・^_^;　ディープな事案。

数学ってのは不思議にうまくできてます。

人間が「全ての有限数を超える、理論的最強」みたいな
悪魔的な関数を作ろうとすると、
絶対に何か不具合が出てきて
計算できないようになってるんですねー。

そうなってます。



次回予定：
BX関数より大きな数を紹介します。^^;

しかもその数はわりと身近。
誰でも絶対に一度は見たことあると思います。
あるんです。そんな数が。