検索に移動この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。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は存在しない、という定理である。H(A,x)はYESを出力する。H(A,x)はNOを出力する。証明[編集]停止性問題を解くプログラムHが存在すると仮定して矛盾を導く。証明は嘘つきのパラドックスに類似している。M(A)を、H(A,A)=YESならM(A)自身は停止せず、H(A,A)=NOなら0を出力してM(A)を停止するプログラムとする。(H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。)M(M)は停止するだろうか?M(M)が停止したとすると、Mの定義よりH(M,M)=NO。H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。M(M)が停止しないとすると、Mの定義よりH(M,M)=YES。Hの定義より、H(M,M)=YESとなるのはM(M)が停止するときのみなので、矛盾。よって停止性問題を解くプログラムHは存在しない。カントールの対角線論法との関係[編集]対角線論法は、集合Sからその冪集合P(S)への全単射が存在しない(カントールの定理)事を示す為にゲオルグ・カントールが使った論法である。実は上述の証明は対角線論法も利用している。以下簡単の為、プログラムの入力は全て自然数とする。中にはプログラムに対応していないものもあるが、簡単の為その辺の事情は略する。次のように定義する:A(x)が停止すればφ(A,x)=1、そうでなければφ(A,x)=0。以下φ(A,x)の事をφA(x)と定義する。g(A)=¬φA(A)により定義する。ここで「¬」は0と1を反転する写像。すると対角線論法により、g=φMとなるMは存在しない。仮に停止性問題を常に正しく解くプログラムHが存在するとする。M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとすると、MとHの定義よりg=φMが成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。不完全性定理との関係[編集]停止性問題の決定不能性を利用してゲーデルの第一不完全性定理を示すことができる。Σ1述語となるようにできる。停止性問題の決定不能性はこの述語がΠ1述語でないことを述べている。もとで停止しない」という述語はΠ1であるがΣ1でない。述語論理を適当に算術化しておく。ロビンソン算術を含む再帰的かつΣ1健全な理論とする。公理のコードである」という述語が再帰的であることをいう。Σ1健全とは、偽なΣ1文を証明しないことをいう。再帰的可算であり、したがってΣ1述語である。任意のΠ1文を証明または反証すると仮定して矛盾を導く。上でΠ1論理式であることに注意せよ。Σ1完全かつ無矛盾であるからΠ1健全である。