组合逻辑（三）

术语的子递归递归定义如下。

（S1）

m是m的子术语；

（S2）

如果m是n或p的子术语，则m是np的子术语。

顺便说一句，自由变量的概念现在可以直接定义：x是m iff x的自由变量。M的子术语是M的子术语。M的自由变量有时用\ textrm {fv}（m）表示。

所有术语都被解释为函数，组合也是函数。同样，对于一些可以轻松描述和掌握的数值和几何函数，经常遇到的组合器可以被描述为术语上有明显的转换。 （sans serif字母表示组合者，\ mathbin {\ triangleright_1}表示减少一步。）

定义。 （一些著名组合者的公理）

\ textsf {s} xyz \ Mathbin {\ triangleright_1} xz（yz）\ textsf {k} xy \ mathbin {\ triangleright_1} x \ textsf x \ textsf {i}

\ textsf {b} xyz \ mathbin {\ triangleright_1} x（yz）\ textsf {t} xy \ mathbin {\ triangleright_1} yx \ textsf \ textsf {c}

\ textsf {w} Xy \ Mathbin {\ triangleright_1} xyy \ textsf {m} x \ Mathbin {\ triangleright_1} xx \ textsf {y}

\ textsf {j} xyzv \ mathbin {\ triangleright_1} xy（xvz）\ textsf {b}^\ prime xyz \ mathbin {\ triangleright_1} y（xz）

这些公理会默认地指定组合及其还原（或收缩）模式的敏锐度。也许最简单的组合器是应用于参数x的身份组合\ textsf {i}返回相同的x。 \ textsf {k}应用于x是一个恒定函数，因为当它进一步应用于y时，它会产生x，也就是说，即，\ textsf {k}是相对于其第二个参数的cancellator。 \ textsf {w}和\ textsf {m}是重复的，因为在其应用程序的结果中，参数之一（始终）出现两次。[10] \ textsf {c}，\ textsf {t}和\ textsf {v}是排列器，因为它们会更改某些参数的顺序。 \ textsf {b}是一个关联，因为\ textsf {b} xyz变成一个术语，在将y应用于x上之前，将y应用于z。 \ textsf {y}是固定点组合器，因为对于任何功能x，\ textsf {y} x是该函数的固定点（请参阅第2.3节）。 Combinator \ textsf {b}^\ prime是一个关联器和一个排列器，而\ textsf {s}和\ textsf {j}也是重复的。 \ textsf {s}非常特别，它称为强组成组合器，因为当应用于两个函数时，我们说G和F（以该顺序）以及x，然后是结果术语GX（FX）表达G和F的组成都应用于同一参数x。

这些非正式的解释没有提及X，Y，Z，F，G，\ ldots的功能的任何限制。但是，高于上方的公理限制了组合器对变量的适用性。直观地，我们想说的是，给定任何术语，即M and N，\ textsf {w} Mn一步降低到MNN（可能是另一个术语的子术语）。例如，m可能为\ textsf {k}，n可能是yy，然后\ textsf {wk}（yy）\ triangleright_1 \ textsf {k}（yy）（yy）（yy）。后一个术语提出了进一步的一步减少，实际上，我们可能对连续的一步减少感兴趣，例如从\ textsf {wk}（yy）到yy的那些。实现这些目标的一种方法是从标准的不合理逻辑开始（省略反对称规则并添加某些其他公理和规则）正式化CL（理论）。

Cl（\ text {cl} _ \ triangleright）的不合理计算。

m \ triangleright m \ textsf {s} mnp \ triangleright mp（np）\ quad \ textsf {k} mn \ triangleright m

\ dfrac {m \ triangleright n \ quad n \ triangleright p} {m \ triangleright p} \ dfrac {m \ triangleright n} {mp \ triangleright np np np np np np}

Metavariables的使用包含替代（我们在上面用\ textsf {w} mn术语进行了说明）。身份公理和传递性规则暗示\ triangleright是一种及时的反思性关系。最后两个规则将应用描述为在其两个参数位置中单调的操作。 \ text {cl} _ \ triangleright仅包含\ textsf {s}和\ textsf {k}，因为其他组合可以定义它们 - 正如我们已经在第1.2节中提到的那样，并且正如我们更加精确地解释了这一点的尽头。部分。

组合\ {\ textsf {s}，\ textsf {k} \}的组合称为组合基础，也就是说，这两个组合器是\ text {cl} _ \ triangleright的未定义常数。为了在此计算中给出一个证明的想法，可以将以下步骤拼凑在一起，以证明\ textsf {skk}（\ textsf {ksk}）\ triangleright \ triangleright \ textsf {s}。 \ textsf {ksk} \ triangleright \ textsf {s}是一个axiom的实例。然后\ textsf {skk}（\ textsf {ksk}）\ triangleright \ textsf {skks}是通过正确的单调性获得的，此外，\ textsf {skk}（skk}（\ textsf {\ textsf {ksk}） \ textsf {s}和\ textsf {k}公理的实例以及传递性规则的应用程序。

关系\ triangleright称为弱减少，可以或以下定义。 （“弱减少”是CL中使用的一个技术术语，用于将一组术语与其他关系区分开的关系，其中一个被称为“强还原”。）一个词是\ textsf {s}的术语MNP或表格\ Textsf {K} Mn是Redex，并且领先的组合器（\ Textsf {S}和\ Textsf {K}分别是Redexes的头部。如果一个术语q包含\ textsf {s} mnp的次术\ textsf {k} mn和M）即，在两种情况下，q \ triangleright q^\ prime。然后，还原可以定义为一步还原的反射性传递闭合。这个概念由\ text {cl} _ \ triangleright完全捕获。从我们刚刚描述的意义上，\ text {cl} _ \ triangleright证明了ccleculus \ text {cl} _ \ triangleright是完整的，即如果m \ triangleright n，则证明了\ text {cl} _ \ triangleright。相反的含义也是如此。）

还原的概念比一步降低的关系弱，因此使用更牢固的关系来区分术语子类是有用的。一个术语以正常形式（nf）不包含重新形式时。请注意，一步降低不需要减少项包含的重复总数，因此，并非可以通过有限的许多一步减少来将每个项变成NF中的术语。实际上，某些术语不会缩短到NF中的一个术语。

减少可以说是表示函数的术语之间的重要关系。程序执行和其他具体计算中的典型步骤是功能应用程序，而不是朝另一个方向移动，即所谓的扩展。但是，功能平等的概念是数学中每个人都熟悉的，并且在CL中也引入了类似的概念。一步还原关系的及交易，反身，对称闭合称为（弱）平等。可以通过使用表征组合常数和应用程序操作的组合公理和规则扩展标准方程逻辑来获得方程CL的形式化。

Cl（\ Text {Cl} _ =）的方程计算。

m = m \ textsf {k} mn = m \ quad \ textsf {s} mnp = mp（np）\ quad

\ quad \ dfrac {m = n \ quad n = p} {m = p} \ quad \ dfrac {m = n} {n = m} \ dfrac {m = n} n} {pm = pn}

第一个公理和前两个规则构成了方程逻辑。常数再次是组合\ textsf {s}和\ textsf {k}。请注意，\ text {cl} _ =可以通过添加对称规则来定义为\ text {cl} _ \ triangleright的扩展关闭。我们选择使用新的符号（并添加对称规则）重复不合适的公理和规则，以使两个定义具有独立且易于掌握。 = =重合的两个特征 - 就像\ triangleright的特征一样。

\ text {cl} _ \ triangleright和\ text {cl} _ =共享一个可能需要或不可能的功能 - 要捕获对功能的理解类型。为了说明问题，让我们考虑单位组合\ textsf {skk}和\ textsf {sk}（\ textsf {kk}）。很容易验证\ textsf {skk} m \ triangleright m和\ textsf {sk}（\ textsf {kk}）m \ triangleright M.但是，\ triangleright M.都不是\ textsf {skk} \ triangleright textsf {kk}）nor \ textsf {sk}（\ textsf {kk}）\ triangleright \ textsf {skk}在\ text {cl} _ \ triangleright中可证明一个fortiori，在\ text {cl} _ =中不可证明的两个术语的平等。这意味着\ text {cl} _ \ triangleright和\ text {cl} _ =正式化功能的强度概念，其中“ intensionality”意味着在同一输入上给出相同输出的函数可能仍然可以区分。

一个可能遇到的原型强度功能是算法。作为示例，我们可能会想到各种规格来计算\ pi的小数扩展或以相同方式行为的各种计算机程序。例如，编译器（对于一种和同一语言）可能会通过使用或不使用某些优化而彼此差异，从而从给定的代码中产生程序，这些代码具有相同的输入 - 输出行为但运行时间不同。

如果要识别从其输入 - 输出行为的角度来看的函数，也就是说，寻求对功能的扩展理解，那么\ text {cl} _ \ triangleright和\ triangleright and \ text {cl} _ =已经要按以下规则扩展（其中符号\ ddagger将分别替换为\ triangleright或=）。

\ frac {mx \ ddagger nx} {m \ ddagger n} \ text {其中} x \ text {在} mn中不自由。

2.2教堂 - 跨性别定理和一致性定理

上一节的计算\ text {cl} _ \ triangleright和\ text {cl} _ =正式化降低和平等。但是，\ triangleright and =在认为术语代表函数时具有一些重要的属性。下一个定理是关于CL的最早，最著名的结果之一。

教堂 - rosser定理（i）。如果M减少为n和p，则n和p都会减少一个项q。

图1

图1。教会定理的插图（i）

如果我们认为减少就像计算函数的价值，那么可以认为教会 - 划线定理（第一个近似值）可以指出，一系列术语计算的最终结果是独特的 - 独特的步骤。但是，这是一个轻微的夸大，因为唯一性意味着每个系列的计算结束（或术语中的“循环”）。也就是说，如果有唯一的最终术语，则只有有限的许多连续计算步骤是可能的。

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