λ-calculus.λ計算.(lambda calculus)

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 00:45:53

λ計算について議論しましょう．
とりあえず，λ計算の基本から，各種関数型言語との関係，さらには研究ネタ
まで，λ計算に関係の深い話題ならなんでも OK ということで．

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 00:47:18

どなたかβ変換の基本について教えてください．
(λx.x)((λx.x)x) というλ式のβ変換には複数
の変換の仕方があると思うのですが，たとえば，

(λx.x)((λx.x)x)
　　　　^^^^^^^
->(λx.x)x
^^^^^^^
->x

の場合と，

(λx.x)((λx.x)x)
^^^^^^^
->((λx.x)x)((λx.x)x)
　^^^^^^^^^^
->x((λx.x)x)
　　^^^^^^^
->xx

とで結果が異なってしまいます．
どこで間違えているのでしょうか?

2 · 2006/12/08(金) 00:50:16

すいません，書き忘れました．

(λx.x)((λx.x)x)
　　　　^^^^^^^
の ^^^^ 部分は，注目しているβ基を表しています．

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 01:11:53

> (λx.x)((λx.x)x)
> ^^^^^^^
> ->((λx.x)x)((λx.x)x)
いくらなんでもこの簡約はありえないだろ常識的に考えて。。。

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 01:30:41

>>4
ぐはぁ，ホントだ．．．
早速ありがとうございました．

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 01:49:33

日本語英語を問わず，初学者向けに基礎から解説している文献があったら
教えていただけませんか? アマゾンの書評を見て，

高橋正子,『計算論：計算可能性とラムダ計算』, ISBN4-7649-0184-6, 1991

を買ってみたんですが，自分には難しすぎて独習は絶望的に思えます．

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 03:10:37

>>6
コンピュータサイエンス入門の紫のやつ

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 09:11:50

>>7
Scheme を題材にした SICP のことでしょうか?
(http://jargon.net/jargonfile/p/PurpleBook.html)
だとすると，Church number は扱っていますが, Church-Rosser
の定理などは扱っていないので，これだけではλ計算の勉強には
不十分に思えます．
それとも別の本のことですか?

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 09:46:08

>>6
高橋正子が無理なら渡辺米崎のがいいよ。
『計算論入門』渡辺治米崎直樹日本評論社 2100円

λの勉強してどういう方向に行きたいのかにもよるが。

**名無しさん＠お腹いっぱい。** · 2006/12/08(金) 11:36:11

>>8
違う違う
http://www.amazon.co.jp/gp/product/4000050060