以前取り上げたY Combinatorですが、何故"Y"なのかと思って調べてみたところ、どうやら"To Mock a Mockkingbird" がもとになっているようです。 この本では色々な鳥の名前を各ラムダ式に割り当てて、組み合わせ理論(Combinatory Logic)を解説しています。 ちなみにYは"Why Bird (aka Sage Bird)"だそうで。 さて、組み合わせ理論の有名な話として、 K = λxy.x S = λxyz.xz(yz) の二つを用いることで、チューリングマシンと等価な計算能力が得られるということが知られています(ということは、この二つさえあれば、今一般に使われているプログラムは全て記述できるわけですね)。 例えば、恒等写像I(λx.x)は SKK = (λxyz.xz(yz))(λxy.x)(λxy.x) = (λyz.(λxy.x)z(yz))(