Monday, June 3, 2013

SKIP: Probabilistic SKI combinator calculus

Add to the S, K, and I combinators of the SKI combinator calculus the P combinator:

Sxyz = xz(yz)
Kxy = x
Ix = x
P = K or KI with equal probability (0.5)

It follows that Pxy evaluates to Kxy or KIxy, then to x or Iy = y with equal probability.

see also Evolutionary code and the probabilistic lambda calculus
and a SKI fixed-point combinator