トップ «前の日記(2008-06-11) 最新 次の日記(2008-06-14)» 編集

Route 477



2008-06-12

[lisp] 純Lispは関数5つだけでどうやってチューリング完全になるのか?

Wikipediaの「純Lisp」の項を見ると、5つの基本関数だけでチューリング完全だよーみたいなことが書いてある。 でも実際にはcar/cdr/cons/eq/atomだけじゃ分岐も再帰もできなくね?という疑問をどっかで見て、リンクされてる論文を 見てみたりもしたけどよく分かんなかったのだけど、 id:kazu-yamamotoさん講演資料を見てようやく分かった。

5つの関数
 car 
 cdr 
 cons 
 eq 
 atom 
2つの特殊形式
 quote 
 cond 
関数定義の機能     
 lambda 
 label (defineのこと)

要するに、condとかは特殊形式だから「5つの基本関数」には入らないと(笑)。まぁそりゃそうだけどさ。