组合逻辑（五）

Haskell B. Curry和Alan Turing都定义了固定点组合器（在Cl或\ Lambda-Calculus中）。如果我们考虑定义

\ textsf {y} _1 = \ textsf {bm}（\ textsf {bwb}）\ quad \ textsf {y} _2 = \ textsf {w}（\ textsf {\ textsf {b}（b}） ）））（\ textsf {w}（\ textsf {b}（\ textsf {bw}（\ textsf {bt}）））））））））））

（添加下标以区分两个定义），然后我们可以看到\ textsf {y} _1 m = m（\ textsf {y} _1m），但对于\ textsf {y} _2，_2，\ textsf {y} {y} _2m \ triangleright m（\ textsf {y} _2m）也容纳。在这方面，\ textsf {y} _1类似于库里的固定点组合器（实际上，与任何固定点组合符）相似，而\ textsf {y} _2就像图灵的固定点组合器一样。

固定点定理在一定程度上证明了Cl的表达能力。但是，固定点组合符可以从没有取消器的基础上定义（如\ textsf {y} _1和\ textsf {y} _2 show）。 Cl的全部功能（带有基本\ {\ textsf {s}，\ textsf {k} \}）的全部功能由以下定理阐明。

定理。 （组合完整性）如果f（x_1，\ ldots，x_n）= m（其中m是包含其他变量的术语，则没有明确列出的变量），则有一个comminator \ textsf {x} \ ldots x_n减少为M。

可以加强定理的假设，以排除M中未发生X的某些出现的可能性，那么可以通过添加\ textsf {x}的资格来加强结果，更具体地，更具体地，\ textsf {x} {x}是\ {\ textsf {b}，\ textsf {w}，\ textsf {c}，\ textsf {i} \}的组合器{x}是\ {\ textsf {i}，\ textsf {j} \}的组合器。 （这些基础对应于教堂的首选\ lambda \ textsf {i} -calculus。）。

组合完整性通常通过在 CL 中定义“伪”\lambda-抽象（或括号抽象）来证明。有多种算法可以在 CL 中定义括号抽象运算符，其行为类似于 lambda 演算中的 lambda 运算符。该运算符通常用 [\,] 或 \lambda^* 表示。这些算法在各个方面都有所不同：（i）它们预设的组合器集合，（ii）结果术语的长度，（iii）它们是否与将组合术语翻译成的算法组成（句法）一致。一个 lambda 项，以及 (iv) 它们是否与约简或等式交换。

第一个算法的元素可能已经在 Schönfinkel (1924) 中找到，它由以下条款组成，这些条款按其列出的顺序应用。

\begin{align} \tag{k} &[x].\,M=\textsf{K}M, \text{ 其中 } x\notin\textrm{fv}(M) \\ \tag{i} & [x].\,x=\textsf{I} \\ \tag{\(\eta\)} &[x].\,Mx=M, \text{ 其中 } x\notin\textrm{fv}( M) \\ \tag{b} &[x].\,MN=\textsf{B}M([x].\,N), \text{ 其中 } x\notin\textrm{fv}(M) \\ \tag{c} &[x].\,MN=\textsf{C}([x].\,M)N, \text{ 其中 } x\notin\textrm{fv}(N) \\ \tag{s} &[x].\,MN=\textsf{S}([x].\,M)([x].\,N) \end{对齐}

例如，如果该算法应用于项 \lambda xyz.x(yz) （即 \textsf{B} 的 lambda 翻译），则结果项为 \textsf{B}。然而，如果省略 eta，则会产生更长的结果，即 \textsf{C}(\textsf{BB}(\textsf{BBI}))(\textsf{C} (\textsf{BBI})\textsf {我}）。另一种算法例如由(i)、(k)和(s)项组成。

3. 非经典逻辑和类型化 CL

3.1 简单类型

组合项被认为是函数，并且函数被认为具有域（一组可能的输入）和共域（一组可能的输出）。例如，如果将一元函数视为一组有序对，则域和余域分别由第一和第二投影给出。如果允许部分函数和非本体函数，则由第一和第二投影产生的集合的超集也可以是域和共域。范畴论，其中函数是范畴的组成部分（没有假设集合论约简），保留了域和共域的概念；此外，每个函数都有唯一的域和辅域。

具有相同域和共域的函数可能完全不同，但是，通过抽象，它们具有相同的类别或类型。作为一个简单的说明，令 f_1 和 f_2 是两个函数，定义为 f_1= \lambda x.\,8\cdot x 和 f_2=\lambda x.\,x/3。如果 x 是实数范围内的变量，则 f_1 和 f_2 具有相同的域和余域（即，它们具有相同的类型 \mathbb{R}\rightarrow\mathbb{R}），尽管 f_1\ne f_2，因为 f_1( x)\ne f_2(x) 每当 x\ne0 时。表示函数 f 以 A 为定义域、以 B 为余域的通常表示法是 f\colon A\rightarrow B。现在 '\rightarrow' 经常在逻辑中用作蕴涵或蕴涵的符号，这是一个令人高兴的巧合。 （非古典）含义。

给定一组基本类型（我们用 P 表示），类型定义如下。

如果 p\in P 则 p 是一种类型；

如果 A,B 是类型，则 (A\rightarrow B) 是类型。

为了将这些类型与其他类型（其中一些类型将在下一节中介绍）区分开来，它们被称为简单类型。

组合子和类型之间的联系可以用恒等组合子的例子来解释。复合组合项是通过应用运算形成的。肯定前件的前提可以通过融合来连接（用 \circ 表示），这就像最强相关逻辑 B 中的应用操作。 \textsf{I}x \triangleright x 所以如果 x 的类型是 A，则 \textsf{ I}x 的类型应该隐含 A。此外，对于某些类型 X，\textsf{I}x 的类型应该是 X\circ A 的形式；那么 \textsf{I} 可以是 A\rightarrow A 类型。在这个例子中，我们固定了 x 的类型，但是， \textsf{I} 可以应用于任何项，因此，更准确的说法是 A\rightarrow A是\textsf{I}的类型模式，或者说\textsf{I}的类型可以是任何自蕴含形式的公式。

类型分配系统 TA_\textrm{CL} 被正式定义为以下推导系统。 （当蕴涵公式被视为类型时，通常的约定是通过与右侧关联来省略括号。）

\Delta\vdash\textsf{S}\冒号(A\右箭头 B\右箭头 C)\右箭头 (A\右箭头 B)\右箭头 A\右箭头 C \Delta\vdash\textsf{K}\冒号 A \右箭头 B\ rightarrow A \frac{\Delta\vdash M\colon A\rightarrow B \quad\Theta\vdash N\colon A} {\Delta,\Theta\vdash MN\colon B}

上面 M\colon A 形式的表达式称为类型赋值。类型分配系统的一个特征是，如果 M\colon A 可证明，则 A 被认为是可以分配给 M 的类型之一。但是，可证明的分配并不排除其他类型与同一类型相关联。术语 M，即类型赋值，并不严格固定术语的类型。 \vdash 左侧的 \Delta 和 \Theta 是变量的类型分配集，并且假定它们是一致的，这意味着任何变量都不能分配两种或多种类型。

类型分配系统通常称为柯里式类型系统。输入术语的另一种方法是固定每个术语的类型，在这种情况下，每个术语只有一种类型。这种演算被称为丘奇式打字系统。然后，例如，类型的恒等组合符 \textsf{I}

(A\右箭头 A\右箭头 A)\右箭头 A\右箭头 A\右箭头 A

与类型的恒等组合符 \textsf{I} 不同

((B \右箭头 B)\右箭头 B)\右箭头(B\右箭头 B)\右箭头 B.

这两种打字风格有很多共同点，但它们之间也存在一定的差异。特别是，在 Church 风格的打字系统中，没有自应用程序是可打字的，而其中一些术语可以在 Curry 风格的打字系统中分配类型。事实证明，柯里式类型系统在建立 CL 和 lambda 演算的各种属性方面非常有用。另一方面，Church 风格的类型更接近地模拟某些函数式编程语言（没有对象）中的类型。

在这两种类型中，类型和组合符之间不存在一一对应关系：并非所有组合符都可以分配类型，并且某些蕴涵公式不能分配给任何组合项。可以分配类型的组合器称为可打字的，可以分配给组合器的类型称为可居住的。例如， \textsf{M} 没有（简单）类型，因为蕴涵公式永远不会与其自身的先行词相同。另一方面，皮尔士定律 ((A\rightarrow B)\rightarrow A) \rightarrow A 不是类型赋值系统 TA_\textrm{CL} 中任何组合器的类型。尽管（或者实际上是由于）蕴涵公式和组合项之间存在差异，但可以分配给某些组合项集合的蕴涵公式类别与一些重要逻辑的定理集合一致。

A\rightarrow B 是直觉蕴涵逻辑定理，用 IPC_\rightarrow 或 J_\rightarrow 表示，当且仅当对于某个 M，M\colon A\rightarrow B 是 TA_\textrm{CL} 中的可证明类型赋值，其中项 M 由 \textsf{S} 和 \textsf{K} 构建，即 M 是基 \{\textsf{S},\textsf{K}\} 上的组合器。

包含蕴涵定理的组合器在演绎系统 TA_\textrm{CL} 中对该定理的证明进行编码。有一种算法可以恢复构成组合器类型证明的公式，此外，该算法产生最小且结构良好的证明。直觉逻辑的蕴涵定理（及其证明）与可类型化封闭 lambda 项（或组合子）之间的对应关系称为柯里-霍华德同构。希尔伯特式公理系统中证明的通常概念相当宽松，但可以对其进行整理以获得遍历证明的概念。在遍历证明中，组合器的子项与遍历证明中的公式以及其中的应用程序和分离之间存在一一对应关系（参见 Bimbó 2007）。

上述对应关系可以针对其他蕴涵逻辑和组合基进行修改。下一个定理列出了相关逻辑 R 和 T 的蕴涵片段与一些本身感兴趣的组合基之间获得的对应关系。

A\rightarrow B 是 R_{\rightarrow} (或 T_{\rightarrow}) 的定理，当且仅当对于某些 M，M\colon A\rightarrow B 是可证明的类型赋值，其中 M 是 \{\textsf 上的组合子{B}, \textsf{I},\textsf{W},\textsf{C}\} （或超过 \{\textsf{B},\textsf{B}^\prime, \textsf{I},\ textsf{S},\textsf{S}^\prime\})。

微积分 \textrm{TA}_\textrm{CL} 可以通过添加两个基中的组合子的公理模式来修改。 （不在这些基中的组合器的公理模式可以从微积分中省略，或者在证明中简单地可以忽略。）新公理如下。

\begin{align*} \textsf{B} &\colon (A\rightarrow B)\rightarrow(C\rightarrow A)\rightarrow C\rightarrow B \\ \textsf{B}^\prime &\colon (A\右箭头 B)\右箭头(B\右箭头 C)\右箭头 A\右箭头 C \\ \textsf{C} &\冒号 (A\右箭头 B\右箭头 C)\右箭头 B\右箭头 A\右箭头 C \\ \textsf{ W} &\冒号 (A\右箭头 A\右箭头 B)\右箭头 A\右箭头 B \\ \textsf{S}^\prime &\冒号 (A\右箭头 B)\rightarrow(A\右箭头 B\右箭头 C) \rightarrow A\rightarrow C \\ \textsf{I} &\colon A\rightarrow A \end{align*}

组合基 \{\textsf{B},\textsf{C},\textsf{W},\textsf{I}\} 特别有趣，因为这些组合符足以定义一个括号抽象，它等价于lambda-textsf{I}-演算的抽象。换句话说，所有依赖于其所有参数的函数都可以由此基定义。另一个基础允许定义可以用所谓的遗传权利最大项类别中的项来描述的函数（参见 Bimbó 2005）。通俗地说，这些术语背后的想法是，函数可以被枚举，然后它们的连续应用应该形成一个索引“全局递增”的序列。

类型分配有两部分：术语和公式。某个术语是否可以分配类型以及某种类型是否可以分配给某个术语的问题分别是可打字性问题和居住问题。尽管这些问题可能是针对一组相同的类型分配提出的，但这些问题的计算属性可能差异很大。

如果一个术语M可以被分配一个类型，即M是否是可打字的，那么它是可判定的。

该定理以相当一般的方式表述，没有具体指定假设的组合基或 TA_\textrm{CL} 的哪种修改，因为该定理对任何组合基都成立。事实上，有一种算法可以给定一个组合器来决定该组合器是否是可打字的，并且对于可打字的组合器也产生一个类型。当然，在组合完备基 \{\textsf{S},\textsf{K}\} 中，所有组合子都可以表示为仅由这两个组合子组成的项。然而，这个假设对于可打字性的解决方案来说并不是必需的，尽管它可能为通用算法的存在提供了解释。

居住问题没有类似的通用解，因为组合项相等的问题是不可判定的。给定一组公理模式，这些公理模式是以分离作为推理规则的组合器类型，逻辑的可判定性问题可以被视为居住问题。事实上，如果 A 是一个蕴涵公式，那么判断 A 是否是一个定理就等于确定是否存在一个项（在对应于公理模式的基础上）可以将 A 指定为其类型。 （当然，更复杂的算法实际上可能会产生这样的项，在这种情况下，很容易通过重建定理的证明来验证主张的正确性。）

为了了解在可判定性的情况下从哪里会出现复杂性，我们比较了项的形成规则和分离规则。给定组合基和可枚举变量集，可以通过检查某个项是否在生成的项集中来确定。也就是说，规则的所有输入都作为结果项的子项保留在输出中。相反，分离的应用产生的公式是大前提的真子公式（并且在特殊情况下，当大前提是自我同一性的实例时，它与小前提相同）。缺乏通过应用前件来保留前提的所有子公式是某些蕴涵逻辑决策问题困难的罪魁祸首。因此，对于许多可判定逻辑来说，存在一个利用顺序微积分的判定过程，其中割定理和子公式性质成立，这也就不足为奇了。居住问题的解决方案可能会遇到与一般可判定性问题中出现的困难类似的困难。

例如，组合子 \textsf{K} 可以分配以下类型。

p\rightarrow(q\rightarrow(q\rightarrow q\rightarrow q)\rightarrow(q \rightarrow q)\rightarrow q\rightarrow q)\rightarrow p

\textsf{SKK} 可以被指定为类型 p\rightarrow p。 TA_\textrm{CL} 中有一个以 \textsf{SKK}\colon p\rightarrow p 结尾的证明，不包含上面的长公式。然而，有一个 \textsf{SKK}\colon p\rightarrow p 的证明，其中包含上述公式，其第二个先行词不是 p\rightarrow p 的子公式，实际上，两个公式的子公式的集合为脱节。 （我们选择了两个不同的命题变量，p 和 q 来强调这一点。）然而，居住问题的一些重要情况是可以判定的。

如果一个类型在基 \{\textsf{S},\textsf{K}\} 上有一个居民，那么它是可判定的。

该定理相当于直觉逻辑蕴涵片段的可判定性的类型化版本，它是 Gentzen 可判定性结果的一部分（可追溯至 1935 年）。

如果一个类型在基 \{\textsf{I},\textsf{C},\textsf{B}^\prime,\textsf{W}\} 上有居民，则它是可判定的。

该定理是相关蕴涵逻辑的蕴涵片段的可判定性的类型化等价物。 R_{\rightarrow} 的可判定性由 Saul A. Kripke 于 1959 年与密切相关的 E_{\rightarrow} （蕴涵逻辑的蕴涵片段）的可判定性一起证明。

如果一个类型在基 \{\textsf{B},\textsf{B}^\prime,\textsf{I},\textsf{W}\} 上有居民，则它是可判定的。

该定理是票蕴含逻辑 T_\rightarrow 的蕴涵片段的可判定性的类型化版本，已与 R_\rightarrow（R_\rightarrow 与真值常数 t）和 T_\rightarrow^ 的可判定性一起得到证明。 \textbf{t}（T_\rightarrow，真值常数 t）——Bimbó 和 Dunn (2012) 以及 Bimbó 和 Dunn (2013)。 Padovani (2013) 中有一个独立的结果（仅适用于 T_\rightarrow），它扩展了 Broda 等人的研究。 （2004）。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。