マンガ6.b「停止性問題」

コンピュータと不完全性定理の関係です。

LabyAI_BTN
↑マンガごっちゃに置かせてもらっています。

プログラミングをしていると、同じところをぐるぐる回って、永遠に止まらないプログラム、というのを書いてしまうことがあります。当然いつまでたっても答えが出ないので、うれしくない状況です。

では、全部のプログラムが「止まるか、止まらないか?」を判断することはできるのか?
…という問題が、実は不完全性定理と同じ話ですよ、というのをチューリングが見つけています。