チューリングマシンの停止問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
チューリングマシンの停止問題（チューリングマシンのていしもんだい）は、与えられたチューリング機械（算譜、算法）eと文字列xについて、xを入力とするeの計算が停止（終了）するか否かを問う判定問題である。単に停止問題（halting problem）ともいう。
アラン・チューリングは1936年、停止問題を解くチューリング機械が存在しないことを対角線論法で示した。すなわちそのようなチューリング機械の存在を仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリング機械が構成できるという矛盾が導かれる。
[編集] 関連項目
 |
この項目「チューリングマシンの停止問題」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル 数学／ウィキプロジェクト 数学） |
