「数学コラム チューリングの停止問題の証明 パート3 （2020/05/17)」
チューリングの停止問題：
「万能ループ判定機は存在しない」を証明します。パート3
前回までのお話：
仮に万能ループ判定機
isTerminate(string function ,object parameter)
が存在するならば、
IsTerminate関数は
string functionの中に
記述された関数fnにつき
fn(parameter) がコンピューターで実行されたときに、
それが有限時間内で終了するのか、
しないのかをboolで返す。
isTerminate(string function ,object parameter)
が存在するならば、
IsTerminate関数は
string functionの中に
記述された関数fnにつき
fn(parameter) がコンピューターで実行されたときに、
それが有限時間内で終了するのか、
しないのかをboolで返す。
このときに我々は
string functionX =
@"
void fnX(string fn)
{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
";
を考案します。@"
void fnX(string fn)
{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
";
それではいよいよ証明のファイナルパート。
fnX(functionX)
を実行するとどうなるでしょう・・・か！
その前に・・・そもそも
fnX(functionX)
とはいったい何だ。 ごごご。
関数fnXの中に、fnXの設計図functionXを突っ込むなんて
意味がわからん。^^A;
Q.そもそもそんな事していいの？
A.問題ありません
fnXは
void fnX(string fn)
であり、string型の引数を受け取る関数。
それ以外の何者でもない。
string fnの値がなんであろうと全く構いません。
なので、
void fnX(string fn = functionX)
のようにfnX自身の設計図functionXを
引数に突っ込む事に何も問題はありません。
void fnX(string fn)
であり、string型の引数を受け取る関数。
それ以外の何者でもない。
string fnの値がなんであろうと全く構いません。
なので、
void fnX(string fn = functionX)
のようにfnX自身の設計図functionXを
引数に突っ込む事に何も問題はありません。
それでは、
fnX(functionX)
を実行するとどうなるでしょうか。
このコードは以下と同等になります。
bool fnX(string fn = functionX)
{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
↓{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
bool fnX(object fn = functionX)
{
for (;;)
{
if (! isTerminate(functionX,funcionX)) break;
}
}
{
for (;;)
{
if (! isTerminate(functionX,funcionX)) break;
}
}
我々は
isTerminate(functionX,funcionX)
の値がなんであるかを知りません。
ただ万能ループ判定機isTerminateは
bool isTerminate(string fn)
であり、trueかfalseのどちらかを確実に返してくれるのはわかってます。
それでは仮に
isTerminate(functionX,funcionX)==true
と仮定しましょう。
ならば
fnX(functionX)
↓
bool fnX(object fn = functionX)
{
for (;;)
{
if (! isTerminate(functionX,funcionX)) break;
}
}
↓{
for (;;)
{
if (! isTerminate(functionX,funcionX)) break;
}
}
bool fnX(object fn = functionX)
{
for (;;)
{
if (! true) break;
}
}
↓{
for (;;)
{
if (! true) break;
}
}
bool fnX(string fn = functionX)
{
for (;;)
{
;
}
}
{
for (;;)
{
;
}
}
結論としては
fnX(functionX)
は無限ループ。このプログラムは明らかに終了しません。
だが仮定により
isTerminate(functionX,funcionX) == true
であった。
つまり、万能ループ判定機isTerminateは
fnX(functionX)は「有限時間内に終了する」
と予告していたのにも関わらず、実際には終了しない。
isTerminate関数は予想を間違えました。
それでは逆に
isTerminate(functionX,funcionX) == false
を返すと仮定します。
その場合は
fnX(functionX)
↓
bool fnX(string fn = functionX)
{
for (;;)
{
if (! isTerminate(functionX,functionX)) break;
}
}
↓{
for (;;)
{
if (! isTerminate(functionX,functionX)) break;
}
}
bool fnX(string fn = functionX)
{
for (;;)
{
if (! false) break;
}
}
↓{
for (;;)
{
if (! false) break;
}
}
bool fnX(string fn = functionX)
{
for (;;)
{
break;
}
}
↓{
for (;;)
{
break;
}
}
bool fnX(string fn = functionX)
{
;
}
{
;
}
これは有限時間内に終了する。
だが仮定により
isTerminate(functionX,funcionX) == false
万能ループ判定機isTerminateは
fnX(functionX)は「有限時間内に終了しない」
と予告していたのにも関わらず、実際には終了した。
isTerminate関数は予想を間違えました。
結局の所、
isTerminate(functionX,funcionX)
の答えがtrueであろうともfalseであろうとも実際の
fn(functionX)
の挙動はその逆となり矛盾が発生します。
→ isTerminateは事実とは異なる、間違った答えを返すことがある。
→ これは判定機として機能していない。
よって
万能判定アルゴリズムisTerminate関数は存在しない。
これでチューリングの停止問題が証明されました。□
チューリングの停止問題を証明するとCorollaryとして↓の結果がついてきます。
定理：
証明：
やっと証明が入った・・・
巨大有限数ランク21はuncomputableである。
特にRayo数はuncomputableである。
特にRayo数はuncomputableである。
証明：
ランク21 = [n文字で作成できる式を全て列挙し、その中で最大を調べ、＋1]を作る方式。
→ ところが全ての式を列挙すると無限ループを含んでしまう。
→ 無限ループは計算が終わらないので無限ループ系だけは除外しなければいけないが
→ チューリングの停止問題。万能ループ判定アルゴリズムは存在しないとたった今証明した
→ どれが無限ループで、どれが有限ループかわからない
(わからない事はないが、人間が一つ一つのループを手作業で選別する必要がある。
そして中には人間には解けない難易度の判定も出てくるので、できない)
→ 無限ループの判定/選別/除去が終わってないので、コンピューターで計算ができない
→ ゆえにuncomputableである。
特にRayo数はuncomputableである。 □
→ ところが全ての式を列挙すると無限ループを含んでしまう。
→ 無限ループは計算が終わらないので無限ループ系だけは除外しなければいけないが
→ チューリングの停止問題。万能ループ判定アルゴリズムは存在しないとたった今証明した
→ どれが無限ループで、どれが有限ループかわからない
(わからない事はないが、人間が一つ一つのループを手作業で選別する必要がある。
そして中には人間には解けない難易度の判定も出てくるので、できない)
→ 無限ループの判定/選別/除去が終わってないので、コンピューターで計算ができない
→ ゆえにuncomputableである。
特にRayo数はuncomputableである。 □
やっと証明が入った・・・
ふ～～～ 長かった。
休憩。。。。。。。-_-) ＝3 ;
・・・・
・・・
・・
・
この問題 ＆ 答えの一番シンプルな考え方としては
クレタ人のパラドックス。
クレタ人 「クレタ人は嘘つきである」
と同じです。
※もしクレタ人が本当に嘘つきなら「クレタ人は嘘つきである」は偽である。つまりクレタ人は正直者。矛盾。
クレタ人が本当は正直者なら「クレタ人は嘘つきである」は真である。つまりクレタ人は嘘つき。矛盾。
クレタ人 → fnX
クレタ人「クレタ人は」 → fnX(functionX)
嘘つきである → !isTerminate
と対応してる。両者は全く同じ構造。クレタ人「クレタ人は」 → fnX(functionX)
嘘つきである → !isTerminate
チューリングの停止問題。最短は一行で論破
万能ループ判定機が存在できない根本的な原理はコレ。クレタ人と同じ。
その証明をもっと正式にやったのがパート1～3であったわけです。
次回。パート4。
そもそもこの問題は、
bool isTerminate(string function ,object parameter)
がtrue/falseを返す二値関数であったことが矛盾に繋がったのでした。
それでは、isTerminateを[true/false/それ以外]を返す3値関数にしたら
どうなるでしょうか。
些細な改良に見えますが、これだけでクレタ人理論・論破が通用しなくなる。
全然別のロジックなんですよ。あーらら ^_^;
新 isTerminate関数なら存在できるか？それが問題です。