ゲーデルと論理プログラミング ━━━━━━━━━━━━━━ 1. はじめに K. Godelは数学と論理学の世界に数多くの業績を残したが，その中でもとく に大きなものは，形式的体系の演繹についての完全性定理と不完全性定理，そ して集合論における業績である。ここで紹介するのは，形式的体系についての Godel の２つの定理と論理プログラミングとの関係である。両者の組合せに意 外性を感じる読者もいらっしゃるかもしれないが，論理プログラミングは形式 的体系の定理証明技術をもとにつくられたものであり，２つは深く結びついて いる。 Godel の定理の詳細については別に譲るとして，ここではまずコンピュータ での定理証明の歴史と導出原理を概観し，Horn論理と論理プログラミング，と くにその代表的なものとしてのPrologを述べ，そしてPrologでの対象言語とメ タ言語との関わりから，不完全性定理が

The Super Programming Technique §１．ラムダ式をC++で実現する【前編】 関数型言語の基本的な概念であるラムダ式を、C++で実現する方法について紹介します。 ・高階関数(higher-order function) 他の関数を引数として扱う関数は、高階関数と呼ばれます。 「関数を引数にとる」のですが、関数を渡すためには、C++では、関数ポインタで渡すか、templateで渡すかです。（operator ( )をオーバーロードしたクラスをfunctorと呼び、これを引数templateを用いて渡すテクニックについては⇒集中講義４． 超高速描画の謎【後編】を参照のこと。） グラフィックの転送ルーチン等は、処理の９９％が同じで、ピクセルをコピーする関数のみが違うという場合があります。このように、共通の処理がある場合、この高階関数にすると処理がすっきり書けます。

Hofstadter『メタマジック・ゲーム』 ミンスキー「ゲーデルはLispを思いついておくべきだった。もし彼がLispを思いついていたならば彼の不完全性定理の証明はもっと簡単なものになっていただろう」 ゲーデルの証明の一番難しいところは、数学的体系に自分自身を語らせるところにある。天才のひらめきが何段階か必要になる。しかし、Lispは、少なくともゲーデルが必要としていた意味で、まさに自分自身を直接語ることができる ゲーデルはLispを発明した！ 不完全性定理のLisp, Mathematicaによる記述 和田英一「Lispへのこだわり」(PDF) Eric S. Raymond「ハッカーになろう」LISP は、それをモノにしたときのすばらしい悟り体験のために勉強しましょう。この体験は、その後の人生でよりよいプログラマーとなる手助けとなるはずです。たとえ、実際には LI

Lisp code / Mathematica notebook プログラミング言語なんてどれも同じと思っている人は下の3つをJavaやC++で書いてみてほしい 不完全性定理についてのゲーデルの証明 停止問題の解決不可能性についてのチューリングの証明 LISP式がエレガントであることを証明できないというチャイティンの証明 ライプニッツ「役に立たないパラドックスは無い」（チャイティン「知の限界」） ミンスキー「ゲーデルはLispを思いついておくべきだった。もし彼がLispを思いついていたならば彼の不完全性定理の証明はもっと簡単なものになっただろう」（ホフスタッター「メタマジック・ゲーム」） 次の2冊の本はLispといってもSchemeのようなオリジナル言語が使われている。ここではCommon LispとEmacs Lisp、Mathematicaで書き直した（The Unkn

Last update 1999/08/07 Scheme処理系の制作 第3回 (C)平山直之 無断転載は禁止、リンクはフリー 誤字脱字の指摘は歓迎 継続とは 今回は、前回「めんどくせえ」と放棄した継続の概念の説明および実装レポートについて書きたいと思います。 あれからまたインターネット漁ってみたのですが、やっぱりどうも日本語リソースはないらしいので、自力で書いてみることにします（schemeの研究してる学者・学生なんて掃いて捨てるほどいるだろうに……） さて、こんなC言語のコードがあるとします。 void foo(void){ bar(baz( )); bar(0); } C言語を学んだ皆さんなら、このコードがどういう順番に実行されるのかわかりますよね。説明されるまでもなく、 baz( )を呼び出す その戻り値を引数としてbarを呼び出す 0を引数として呼び出す fooの呼び出しもとに帰

The P = NP problem 計算量理論入門(P=NP 問題の紹介)- アルゴリズムの評価と問題の複雑さ アルゴリズムの複雑さ，問題の複雑さを定義し， 同程度に複雑な問題のグループ分けを定義したい． チューリングマシンとよばれる計算機のモデルを定義し， 計算とは何か，問題とは何かについて議論する． つぎに問題の複雑さの尺度を導入し， 問題を複雑さでグループ分けする場合の有名なグループである P と NP を紹介し，重要な未解決問題である P = NP 問題を紹介する． 計算機のモデル 一般に計算とは，コンピュータなどの計算機に入力を与 え，出力を得る過程という意味で使われる． 正しい出力を得る計算が存在するかどうか，すなわち 計算が可能かどうか，また可能であればどれぐらいの時間がかか るのかに興味があるが，これらは計算を行う機械として何を使うかによって変化 する． いろいろな問題