Schemeによる第一不完全性定理の実装 - 未完成な論を綴るブログ『知の限界』という本を買ったら第一不完全性定理をLispで実装する方法が載っていた。しかし、そのコードはSchemeでは動かないように思えたので、Schemeで実装をしてみた。不完全性定理では、コード中の引数に自身のコード渡して、自己言及的なゲーデル文Gを構成して証明するのだが、S式はコードもただのデータなので、こういうことが出来るのかと感心した。本書では、第一不完全性定理以外にも、不動点や停止問題のLisp実装も示されており、それらはここで示すコードと本書を読めばSchemeで実装可能に思う。 ただし、本書は面白いが、第一不完全性定理の説明などはほとんどないため、そもそも第一不完全性定理を知らない場合は、理解するのは難しそうではある。 知の限界[復刻改装版] (00) 作者:グレゴリー・J・チャイティンエスアイビー・アクセスAmazon Schemeによる再実装 Schemeで再実装した
