6

Kコンビネータは定数関数であることを思い出してください。常に最初の引数を返します。

Kxy = x for all y

「モッキンバードをモックする」という本の中で、著者は話す鳥を含む魔法の森の例を示しています。鳥には行動があります：

鳥AとBがあれば、BからAの名前を呼び出すと、Aはあなたに鳥の名前を呼び出すことで応答します。この鳥はABによって指定されます。

森がA、B、Cの3羽の鳥で構成されているとします。少なくとも1羽の鳥がKコンビネータのように振る舞うことは可能ですか？

以下は、魔法の森の鳥の可能な行動のセットを示す表です。最初の列には、森の中の各鳥の名前があります。一番上の行には、各鳥に呼び出される可能性のある名前があります。体は名前に対する鳥の反応です。たとえば、鳥AにAの名前を呼び出すと、鳥AはCで応答します（行2、列2を参照）。簡潔に言えば、AA =Cです。鳥AにBの名前を呼び出すと、鳥AはBで応答します（行2、列3を参照）。簡潔に言えば、AB = Bです。ACの空のスロットにはどのような値を入れる必要がありますか？

   | A    B    C
------------------
A  | C    B
B  | B    B    B
C  | A    A    A

鳥AをKコンビネータのように動作させることができるかどうかを見てみましょう。上記の値のセットは有望に見えます：

  • すべてのyについてAA=CおよびCy=A。つまり、すべてのyに対して（AA）y=Aです。

  • すべてのyについてAB=BおよびBy=B。つまり、すべてのyに対して（AB）y=Bです。

空のスロット（AC）にはどのような値を配置する必要がありますか？すべての場合を考慮してください：

  • AC = Aの場合、Ayの値はすべてのyに対してCでなければなりませんが、これは明らかに誤りです。したがって、Aを空のスロットの正しい値にすることはできません。

  • AC = Bの場合、Byの値はすべてのyに対してCでなければならず、これは明らかに誤りです。したがって、Bを空のスロットの正しい値にすることはできません。

  • AC = Cの場合、Cyの値はすべてのyに対してCでなければなりませんが、これは明らかに誤りです。したがって、Cを空のスロットの正しい値にすることはできません。

したがって、すべてのyについて、条件（AC）y=Cを満たすために空のスロットに値を配置することはできません。

私の知る限り、鳥をKコンビネータのように振る舞わせることは不可能です。あなたが私を間違っていると証明してくれることを願っています。

4

2 に答える 2

1

あなたは正しいです。有限数の鳥が1を超えることは不可能です。

単純な議論は、そのような鳥Kがあった場合、Kのイメージ内のすべての鳥は（定義により）一定であり、K自体を含むすべての鳥は（カーディナリティの議論により）Kのイメージ内にあります。明らかに一定ではありません。

于 2012-06-04T05:49:14.740 に答える
1

私はメンタル裁判官の答えが好きなので、それを得るのに問題がある人のために、私はそれをもっと詳しく説明します。

Gをすべての関数のセットとします。

Fを|F|となるようなサブセットGとします。> 1および∀f∈F（f：F→F）。（Fはあなたの鳥のセットです。）

1FをFの恒等関数とします。

∃k∈F（∀（f、g）∈（F×F）（kfg = f））があるという矛盾があると仮定します。そのようなkを修正します。言い換えれば、∀f∈F（kfは定数）です。定義により、∀f∈F（kkf = k）。したがって、∀f∈F（kは下の補題による左逆数であるためkf = 1 F ）。したがって、∀f∈F（kfは定数で、kf = 1 F）となります。これは、| F |であるため、明らかに不条理です。>1。

補題：kf = kgとなるように（f、g）∈（F×F）とします。kの定義により、∀h∈F（kfh = f）。したがって、∀h∈F（f = kfh =（kf）h =（kg）h = kgh = g）。これは、f=gの場合にのみ発生する可能性があります。したがって、k単射。したがって、kは左逆でなければなりません。

于 2012-06-06T06:56:51.593 に答える