异或可以用SKI组合子表示吗？

Question

我对 SKI-Combinators 有疑问。

异或（异或）只能用

S

和

K

组合子来表达吗？

我有

True = Cancel
False = (Swap Cancel)

哪里

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

Answer 1

布尔值

你的问题在细节上有点不清楚，但你的意思似乎是你有以下布尔值表示：

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 表示为

IF

表达式：

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

可以减少到

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

一些函数组合器

我们有

id = SKK

作为标准，而

not

可以表示为

flip

，因为

flip b t e = b e t = IF b THEN e ELSE t = IF (not b) THEN t ELSE e

。

flip

它自己很参与但可行

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

现在我们只需要想出一种方法来编写一个函数，该函数接受

x

并将其应用于

NOT

和

ID

这两个项。为了到达那里，我们首先注意到如果我们设置

app := id

然后

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

所以，

(flip app) x f = f x

我们快到了，因为到目前为止的一切都表明

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

最后一步是使最后一行在

x

上成为无点。我们可以使用函数组合运算符来做到这一点：

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

compose

的要求是

compose f g x = f (g x)

我们可以通过设置得到

compose f g := S (K f) g

把它们放在一起

总而言之，我们得到了

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)))

Answer 2

是的！ 2020 年，Stephen Wolfram 为所有 16 个双输入布尔函数（包括 XOR）构建了组合器。原来 XOR 可以表示为 s[s[s[s[s]][s[s[s[k]]]][s]]][k] 其中 k 代表值 True 和 s[k]代表值 False.

例如，这里是对 Wolfram 语言的真假运算的 XOR 组合子形式。

true = k;
false = s[k];
ResourceFunction["CombinatorFixedPoint"][s[s[s[s[s]][s[s[s[k]]]][s]]][k][true][false], SKGlyphs -> {s, k}]

它返回预期的输出——真：

k