Probabilistic combinatory logic

From Esolang
Jump to navigation Jump to search

In an ongoing attempt to formulate a Quantum combinatory logic, User:Hppavilion1 started by formulating 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).

Derived Combinators

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!

Computational Class

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.