任意の (x₁, ・・・, x_n) ∈ Nⁿ について、P (x₁, ・・・, x_n） が成立するかどうか──元を並べる関数があるかどうか──を決定する アルゴリズム の作成を 「決定問題 （decision problem）」 と云います。もし、このような アルゴリズム を作ることができるなら、P は帰納的 （計算可能） であるということです （特徴関数を思い起こしてください）。同じように、集合 S ⊆ N についても、任意の (x₁, ・・・, x_n) ∈ Nⁿ に対して、(x₁, ・・・, x_n）∈ S が成立するかどうかを決定する アルゴリズム の作成も 「決定問題」 と云います。もし、集合が自然数以外の元 （メンバー） であれば、ゲーデル 数を使って自然数に対応することができます。そして、決定できる アルゴリズム を作ることができれば、「決定可能 （decidable、あるいは solvable） と云い、そうでなければ 「決定不能 （undecidable、あるいは unsolvable）」 と云います。そして、チューリング・マシーン が停止できるかどうかを判断する アルゴリズム は存在するかどうか──すなわち、なんらかの アルゴリズム は チューリング・マシーンが停止することを判断できるかどうか──という問題が 「停止問題 （halting problem）」 と云われています。その答えは否定的でした──プログラム が停止するか否かを決定する プログラム を作成できない、ということです。つまり、「『決定可能』 を決定する」 プログラム を作成することはできないということ。チューリング・マシーン は概念的な計算機械ではあるけれど、ゲーデル 氏の 「不完全性定理」 を具体的な一般手続きとして示した究極形ですね。 □