|
計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、あるチューリング機械（≒コンピュータプログラム・アルゴリズム）が、そのテープのある初期状態（≒入力）に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。 == 概要 == プログラム''A''にデータ''x''を入力して実行する事を''A''(''x'')と書き、''A''(''x'')が''y''を出力するとき''y''=''A''(''x'')と書く。コンピュータではいかなるデータも0と1の数字で表し、したがってプログラム自身も0と1の数字で表せる。 コンピュータ用語ではこの数値化を「符号化」と呼び、理論計算機科学では「ゲーデル数化」という。以下記号を簡単にする為、プログラムAを数字で表したものも、Aと書く。 よって例えばプログラムA、Bに対し、「A(B)」は、「プログラムBを表す数字をBとし、AにBを入力して実行する」の意である。停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が停止するかどうかを決定せよ」という問題である。 また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。 すなわち以下の性質を満たすプログラム''H''は存在しない、という定理である。 全てのプログラム''A''と全てのデータ''x''に対し、 * ''A''(''x'')の実行は停止する ⇒ ''H''(''A'',''x'')はYESを出力する。 * ''A''(''x'')の実行は停止しない ⇒ ''H''(''A'',''x'')はNOを出力する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「停止性問題」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Halting problem 」があります。 スポンサード リンク
|