We'll say that a combinator A is invertible if there exists A' s.t.

A'(Ax) = A(A'x) = x

For example, Sxyz = xz(yz) is clearly invertible in this sense because we have S'xyz = x(Kz)y and

S'(Sx)yz = Sx(Kz)y = xy(Kzy) = xyz
S(S'x)yz = S'xz(yz) = x(Kyz)z = xyz

However, Kxy = x clearly cannot be because there is no K'x s.t. K'x = xy for all y. Does a set of invertible combinators exist that is Turing-complete?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.