Probabilistic combinatory logic
Difference from traditional combinatory logic
Probabilistic combinatory logic adds one new combinator:
τ accepts two arguments via currying and returns one of them at random (with 50/50 probability).
The author's first idea, the
O combinator was really just stupid:
Oxy=xy|yx. However, if one needs to use it, it maybe can easily be derived from the
C combinator from the B,C,K,W system; however, the author is too stupid to figure that out. To define it, you simply need to define the
=xy combinator that tells if its arguments are equal, then to do some conditionals mumble mumble and voila! You have the R combinator!
PCL is clearly TC by trivial reduction to combinatory logic; however, additionally, PCL is equivalent to a Probabilistic Turing Machine, if the author is correct, by nature.