純Lisp
687 ：デフォルトの名無しさん：2007/07/03(火) 14:32:31
質問です。
アトムとリストと、
car,cdr,cons,atom,eq
これでどうやって足し算が出来たりするのでしょうか?701 ：デフォルトの名無しさん：2007/07/03(火) 22:14:31
687さんは純Lispが五つの基本関数「だけ」で
本当にチューリング完全かどうか
疑問に思ってるんじゃないですか？ちょうど１ヶ月前の自分と同じで
マッカーシーの論文斜め読みしたら
関数は五つで良いけど
→表記も含まれるから
condかifスペシャルフォームも必要みたいに感じました本当に五つの基本関数（と真偽値）「だけ」でチューリング完全なら
自分にも教えてください704 ：デフォルトの名無しさん：2007/07/03(火) 22:35:59
>>701
再帰かループがないとどうにもならんよ705 ：デフォルトの名無しさん：2007/07/03(火) 22:41:00
大前提としてλ式が必要707 ：デフォルトの名無しさん：2007/07/03(火) 22:44:52
http://pc11.2ch.net/test/read.cgi/tech/1177065699/
そうか、lambdaだけでチューリング完全ですね
でもそうすると５関数の立場が…
確かにcar,cdr,cons,atom,eqだけだと、条件分岐とループは出来なそう。
lambdaがあれば、ifとYコンビネータが作れるけど、ラムダ計算自体がチューリング完全であるということは、car,cdr,cons,atom,eqを含むすべての計算が作れてしまうことを意味してるわけで、そう考えると5関数の立場がない。
もしかして、純lispがチューリング完全であるというのは、ラムダ計算がチューリング完全であることが証明される前の過渡期の時期にだけ意味があったことなのかな？
純LISP - Wikipedia
http://ja.wikipedia.org/wiki/%E7%B4%94LISP
純LISPには二種のデータ(リスト、アトム)、及びそれらを操作する五つの基本関数だけが存在する。
以上が最小構成のLISPであり、理論上チューリングマシンと同等の能力（チューリング完全）を持つ。
うーん、やっぱり純Lispって、本当に5関数「だけ」なんだろうか。
また、仮に関数とは別にスペシャルフォームも含むのだとしたら、if,lambda,defun,quote…どこまでを含むんだろう。
