『計算モデル論入門―チューリング機械からラムダ計算へ (Information Science & Engineering (F5))』(井田哲雄、浜名誠)についてのすべてのヨミメモ


チャーチの提案にしたがい、私たちはチューリング機械で計算できることを、アルゴリズムが存在すると言い換える。すると、定理3.1 (停止問題の判定不能性) から、任意のプログラムの任意のデータに対する実行が停止するか否かを判定する一般的なアルゴリズムは存在しないことがわかる。