帰納言語以上の言語
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/17 08:19 UTC 版)
「計算可能性理論」の記事における「帰納言語以上の言語」の解説
しかし、停止しないチューリングマシンの記述を入力として与えられたとき、それを判定するチューリングマシンが永遠に動作することを許容するなら、停止問題は一応解決する。従って、停止問題判定は帰納的可算言語である。しかし、帰納的可算ですらない言語も存在する。 そのような言語の単純な例は、停止判定の補問題である。つまり、全てのチューリングマシンとそれらが停止しない入力の全組合せからなる言語である。この言語が帰納的可算言語でないことを示すため、そのような全チューリングマシンについて停止して答えを返すチューリングマシン M {\displaystyle M} を構築することを考える。このマシンはチューリングマシンとその入力の組合せが停止する場合は永遠に動作し続ける。そして、このマシンの動作をシミュレートするチューリングマシン M ′ {\displaystyle M'} を考える。つまり、入力として M {\displaystyle M} の記述とその入力(別のチューリングマシンの記述とその入力)が与えられる。さらにタイムシェアリングによって M ′ {\displaystyle M'} は M {\displaystyle M} の入力(あるチューリングマシンとその入力)も並行して実行するものとする。 M {\displaystyle M} の入力であるチューリングマシンの記述と入力が停止しない組合せの場合、 M {\displaystyle M} は停止し、そのシミュレーションも停止することになる。従って、 M ′ {\displaystyle M'} は一方のスレッドが停止し、もう一方が停止しないことから停止問題の判定機能を備えることになる。しかし、既に示したように停止問題は判定不能である。この矛盾により、 M {\displaystyle M} が存在するという仮定が誤っていたことがわかる。以上から停止判定言語の補問題は帰納的可算言語ではないことがわかる。
※この「帰納言語以上の言語」の解説は、「計算可能性理論」の解説の一部です。
「帰納言語以上の言語」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。
- 帰納言語以上の言語のページへのリンク