チューリングマシンの停止問題
チューリングマシンの停止問題（チューリングマシンのていしもんだい）は、プログラムの停止問題、停止性問題とも呼ばれ、次のような問題である。
- 次を満たすチューリングマシンは存在するか：任意のプログラム（アルゴリズム）に対し、そのプログラムをチューリングマシン上で実行したとき、そのチューリングマシンが有限実行時間内で停止するかどうかを判定できる。
1936年、アラン・チューリングは、そのようなチューリングマシンが存在しないことを示した。証明の概要は、もしそのようなチューリングマシンが存在すると仮定して、もし自身が停止すると判定されたならば無限ループを行うように設計すれば、これは停止しないから、矛盾するとしたものである。
関連項目
