クワインへの応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
「クリーネの再帰定理」の記事における「クワインへの応用」の解説
再帰定理の使用の古典的な例は Q ( x , y ) = x {\displaystyle Q(x,y)=x} に対するものである。この場合に対応する指標 p {\displaystyle p} は任意に値を入力すると出力が自分自身に一致する計算可能関数である(Cutland 1980: p. 204)。プログラミングの言葉を用いれば、これはクワインとして知られるプログラムの指標に他ならない。 以下ではLispを用いて指標 p {\displaystyle p} が関数 Q {\displaystyle Q} からどのように実効的に得られるかを見る。関数 s11 はSmn定理に対応するLispコードである。 Q は任意の2引数の関数のLispコードに置き換えられる。 (setq Q '(lambda (x y) x))(setq s11 '(lambda (f x) (list 'lambda '(y) (list f x 'y))))(setq n (list 'lambda '(x y) (list Q (list s11 'x 'x) 'y)))(setq p (eval (list s11 n n))) 次の2つの式の結果は等しくなる。p(nil) Q(p, nil) (eval (list p nil)) (eval (list Q p nil))
※この「クワインへの応用」の解説は、「クリーネの再帰定理」の解説の一部です。
「クワインへの応用」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
- クワインへの応用のページへのリンク
