最近、オライリーの「アンダースタンディングコンピュテーション」を読みました。コンピューターサイエンスの素養がない人にも分かりやすく計算について教えるという内容で、細々と写経しながら読み進めていました。 hirak/memo-understanding-computation ・ GitHub この本、8章と9章がとにかく面白くて、特にライスの定理は初めて知ったので、自分なりに理解をまとめておこうと思います。 ※形式的な証明は私もちゃんと理解していないので、直感的な解説になります。 不可能なプログラムは存在する 我々プログラマーは日々コードを書いているわけですが、プログラムで解けない問題は存在するか考えたことはあるでしょうか? ライスの定理は不可能なプログラムがあることを示した定理です。 ライスの定理 - Wikipedia 計算機科学における計算可能関数の理論に関する定理で、 定められた性