停止性問題の決定不能性定理との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/29 18:36 UTC 版)
「ライスの定理」の記事における「停止性問題の決定不能性定理との関係」の解説
ライスの定理は「停止性問題の決定不能性定理」の一般化である。ここで停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が有限時間で停止するかどうかを決定せよ」という問題である。また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。すなわち次のようなプログラムHは存在しない、という定理である。 A(x)が停止する ⇒ H(A,x)はYESを出力して停止する。 A(x)は停止しない ⇒ H(A,x)はNOを出力して停止する。 ライスの定理のFを「fAは⊥を出力しない」にした場合が「停止性問題の決定不能性定理」に一致する事を簡単に確かめられる。
※この「停止性問題の決定不能性定理との関係」の解説は、「ライスの定理」の解説の一部です。
「停止性問題の決定不能性定理との関係」を含む「ライスの定理」の記事については、「ライスの定理」の概要を参照ください。
ウィキペディア小見出し辞書の「停止性問題の決定不能性定理との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 停止性問題の決定不能性定理との関係のページへのリンク
