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

Lisp code / Mathematica notebook

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

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

ミンスキー「ゲーデルは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行で書ける。他にも興味深い話題が多い。
  2. 数学の限界 G. J. Chaitin The Limits of Mathematics. (オンライン版。邦訳は黒川利明訳『数学の限界』)

YABUKI Taro