不完全性定理のLisp, Mathematicaによる記述

Lisp code / Mathematica notebook

プログラミング言語なんてどれも同じと思っている人は下の3つをJavaやC++で書いてみてほしい

• 不完全性定理についてのゲーデルの証明
• 停止問題の解決不可能性についてのチューリングの証明
• LISP式がエレガントであることを証明できないというチャイティンの証明

ライプニッツ「役に立たないパラドックスは無い」（チャイティン「知の限界」）

ミンスキー「ゲーデルはLispを思いついておくべきだった。もし彼がLispを思いついていたならば彼の不完全性定理の証明はもっと簡単なものになっただろう」（ホフスタッター「メタマジック・ゲーム」）

次の2冊の本はLispといってもSchemeのようなオリジナル言語が使われている。ここではCommon LispとEmacs Lisp、Mathematicaで書き直した（The Unknowableで扱われたものだけ）。Allegro CLとxyzzy、Emacs、Mathematicaで確認済み。

1. G. J. Chaitin The Unknowable. （オンライン版。邦訳は黒川利明訳『知の限界』）
   LISPを使って、うそつき・ラッセル・ベリーのパラドックスからゲーデル・チューリング・チャイティンの不完全性定理を導いている。数学が準経験的だという主張がよくわかる（P≠NPを仮定して研究を進めることがその例）。原書(The Unknowable)ならwebで読める。彼がElegant LISP Programsの中で言うには、最も強力な言語はMathematicaで、Lisp interpreterを300行で書ける。他にも興味深い話題が多い。
   • A Hundred Years of Controversy Regarding the Foundations of Mathematics (数学の基礎に関する百年論争)
   • LISP: A Formalism for Expressing Mathematical Algorithms (LISP: 数学アルゴリズムを表現する形式)
   • Godel's Proof of his Incompleteness Theorem （不完全性定理についてのゲーデルの証明）
   • Turing's Proof of the Unsolvability of the Halting Problem （停止問題の解決不可能性についてのチューリングの証明）
   • My Proof that You Can't Show that a LISP Expression is Elegant （LISPがエレガントであることを証明できないという私の証明）
   • Information & Randomness: A Survey of Algorithmic Information Theory （情報とランダムさ：アルゴリズム的情報論概観）
   • Mathematics in the Third Millennium? （数学の第三千年紀）
2. G. J. Chaitin The Limits of Mathematics. （オンライン版。邦訳は黒川利明訳『数学の限界』）
   • Randomness in Arithmetic and the Decline & Fall of Reductionism in Pure Mathematics, 1992 （算術におけるランダム性と純粋数学における還元主義の衰退）
   • Elegant LISP Programs, 1999 （エレガントなLISPプログラム）
   • An Invitation to Algorithmic Information Theory, 1997 （アルゴリズム的情報理論への招待）
   • The Limits of Mathematics, 1996 （数学の限界）
   • Appendix. LISP interpreter in Mathematica （MathematicaによるLISPインタープリタ）
   • More efficient version of omega2 suggested by Veronica Becher, Buenos Aires, May 1998

YABUKI Taro,