XORはSKIコンビネータを使用して表現できますか？

Question

SKI-Combinatorsについて質問があります。

SとKのコンビネータのみを使用してXORを排他的に表現できますか？

私はあなたの質問は細部に少し不明であるが、何を意味することは、あなたが持っているようです

Cancel x y = K x y = x 
Swap: ff x y = S ff x y = ff y x 

Answer 1

ブール

True = Cancel 
False = (Swap Cancel) 

を持っていますブール値の表現に続く：

T := K 
F := S K 

それは以下の削減が保持する意味ので、これは動作します：

つまり

T t e => t 
F t e => e 

、b t eがIF b THEN t ELSE eとして解釈することができます。 IF _ THEN _ ELSE _

の面で

XORだから、この枠組みを与え、どのように我々は、XORを実装していますか？

xor x y := IF x THEN (not y) ELSE y = (IF x THEN not ELSE id) y 

イータ減少し、一部の機能は我々が標準としてid = SKK持っ

コンビネータ、およびnotを表現することができる

XOR x := IF x THEN not ELSE id = x not id 

になることができます。私たちはIF式としてXORを策定することができますflip b t e = b e t = IF b THEN e ELSE t = IF (not b) THEN t ELSE e以降、flipとなります。 flip it self is quite involvedなんとか

flip := S (S (K (S (KS) K)) S) (KK) 

として今、私たちはただxを取り、二つの用語NOTとIDでそれを適用する関数を記述するための方法を把握する必要があります。そこに着くためには、まず私たちは、その後

app f x = (id f) x = f x 

ので、

(flip app) x f = f x 

を

app := id 

を設定した場合、すべてがこれまでに示しているので私たちは、ほとんどがあることに注意してください

こと

((flip app) id) ((flip app) not x) = ((flip app) not x) id = (x not) id = x not id 

最終ステップはthaを作成することです最後のラインはxにポイントフリーです。

((flip app) id) ((flip app) not x) = compose ((flip app) id) ((flip app) not) x 

compose上の要件は、我々は

compose f g := S (K f) g 

設定一緒をすべてを置くことによって得ることができます

compose f g x = f (g x) 

たということです。私たちは、関数合成演算子でそれを行うことができます

T集計O、我々は

xor := compose ((flip app) id) ((flip app) not) 

か、完全に展開しました：

xor = S (K ((flip app) id)) ((flip app) not) 
    = S (K ((flip app) (SKK))) ((flip app) flip) 
    = S (K ((flip SKK) (SKK))) ((flip SKK) flip) 
    = S (K (((S (S (K (S (KS) K)) S) (KK)) SKK) (SKK))) (((S (S (K (S (KS) K)) S) (KK)) SKK) (S (S (K (S (KS) K)) S) (KK)))