サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
iPhone 16
www.iba.k.u-tokyo.ac.jp/~yabuki
すべての評価関数に適用できる効率のよいアルゴリズムは存在しない。 “すべての評価関数”というのは上の例で言えば“すべての”ということである。 この定理を証明する前に、まずよく知られた探索アルゴリズム[5]を挙げて、探索とはそもそもどのようなものなのかを説明しよう。 探索アルゴリズム “探索”というのは問題の解の候補の中からよいものを探し出すことである(同語反復という感じだが)。ここでは次のように、評価関数が定義された問題を解く過程のことを探索と呼ぶことにする。 解の候補の有限集合を、その要素のひとつをとする。 評価関数はから有限集合への写像である(の要素のひとつをで表す)。 の最大値を与えるようなが問題の解で、それを見つけたいのである。 このような探索問題を解くためのアルゴリズムには大きく分けて次の2つがある。 アルゴリズムのように知識を用いて解を構成するもの(適切なヒュ
Up: 不完全性定理のLisp, Mathematicaによる記述 G. J. Chaitin Godel's Proof of his Incompleteness Theorem の例をMathematicaとCommon Lispで書き直した 準備運動 Mathematicaの場合 Schemeの場合(MIT Scheme) Common Lispの場合 ゲーデルの定理 Mathematicaの場合 Schemeの場合(MIT Scheme) Lispの場合 うそつきのパラドックス:「この文はうそである」 ゲーデルの定理:「この命題は証明できない」(真なのに証明できない命題がある) 準備運動 これは自分のコードを出力するプログラムの例でもある Mathematicaの場合 Mathematicaで書くともっともわかりやすいだろう。まず x -> x[x]
Lisp code / Mathematica notebook プログラミング言語なんてどれも同じと思っている人は下の3つをJavaやC++で書いてみてほしい 不完全性定理についてのゲーデルの証明 停止問題の解決不可能性についてのチューリングの証明 LISP式がエレガントであることを証明できないというチャイティンの証明 ライプニッツ「役に立たないパラドックスは無い」(チャイティン「知の限界」) ミンスキー「ゲーデルはLispを思いついておくべきだった。もし彼がLispを思いついていたならば彼の不完全性定理の証明はもっと簡単なものになっただろう」(ホフスタッター「メタマジック・ゲーム」) 次の2冊の本はLispといってもSchemeのようなオリジナル言語が使われている。ここではCommon LispとEmacs Lisp、Mathematicaで書き直した(The Unkn
Hofstadter『メタマジック・ゲーム』 ミンスキー「ゲーデルはLispを思いついておくべきだった。もし彼がLispを思いついていたならば彼の不完全性定理の証明はもっと簡単なものになっていただろう」 ゲーデルの証明の一番難しいところは、数学的体系に自分自身を語らせるところにある。天才のひらめきが何段階か必要になる。しかし、Lispは、少なくともゲーデルが必要としていた意味で、まさに自分自身を直接語ることができる ゲーデルはLispを発明した! 不完全性定理のLisp, Mathematicaによる記述 和田英一「Lispへのこだわり」(PDF) Eric S. Raymond「ハッカーになろう」LISP は、それをモノにしたときのすばらしい悟り体験のために勉強しましょう。この体験は、その後の人生でよりよいプログラマーとなる手助けとなるはずです。たとえ、実際には LI
このページを最初にブックマークしてみませんか?
『http://www.iba.k.u-tokyo.ac.jp/~yabuki/』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く