Công cụ tổ hợp Y "(L L L ...)" của Jan Willem Klop hoạt động như thế nào?

Question

Tôi hiểu what a Y Combinator is, nhưng tôi không hiểu ví dụ này của một combinator "tiểu thuyết", từ Wikipedia page:

 Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L) 

Where: 

    L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

làm việc như thế này?

Answer 1

Bản chất của bộ kết hợp điểm cố định C là C f giảm xuống f (C f). Nó không quan trọng những gì bạn mất cho C miễn là thực hiện điều này. Vì vậy, thay vì

(\y f. f (y y f)) (\y f. f (y y f)) 

bạn có thể chỉ cần cũng mất

(\y z f. f (y y y f)) (\y z f. f (y y y f)) (\y z f. f (y y y f)) 

Về cơ bản bạn cần một cái gì đó có dạng

C t1 t2 ... tN 

nơi ti = C đối với một số i và

C = \x1 x2 .. xN f. f (xi u1 u2 ... xi ... u(N-1) f) 

Các điều khoản khác tj và uj không thực sự "được sử dụng". Bạn có thể thấy rằng số L của Klop có dạng này (mặc dù anh ta sử dụng thực tế là tất cả ti là L sao cho số xi thứ hai cũng có thể là bất kỳ số nào khác xj).