
_START_ARTICLE_
柯里-霍华德同构
_START_SECTION_
对应的起源、范围和结论
_START_PARAGRAPH_
对应可以在两个层面上看到，首先是类比层次，它声称对一个函数计算出的值的类型的断言可类比于一个逻辑定理，计算这个值的程序可类比于这个定理的证明。在理论计算机科学中，这是连接λ演算和类型论的毗邻领域的一个重要的底层原理。它被经常以下列形式陈述为“证明是程序”。一个可选择的形式化为“命题为类型”。其次，更加正式的，它指定了在两个数学领域之间的同构，就是以一种特定方式形式化的自然演绎和简单类型λ演算之间是双射，首先是证明和项，其次是证明归约步骤和beta归约。_NEWLINE_有多种方式考虑柯里-霍华德对应。在一个方向上，它工作于“把证明编译为程序”级别上。这里的“证明”最初被限定为在构造性逻辑中—典型的是直觉逻辑系统中的证明。而“程序”是在常规的函数式编程的意义上的；从语法的观点上看，这种程序是用某种λ演算表达的。所以柯里-霍华德同构的具体实现是详细研究如何把来自直觉逻辑的证明写成λ项。（这是霍华德的贡献；柯里贡献了组合子，它是相对于是高级语言的λ演算是能写所有东西的机器语言）。最近，同样处理经典逻辑的柯里-霍华德对应的扩展可被公式化了，通过对经典有效规则比如双重否定除去和皮尔士定律关联上明确的用续体比如call/cc处理的一类项。_NEWLINE_还有一个相反的方向，对一个程序的正确性关联上“证明提取”的可能性。这在非常丰富的类型论环境中是可行的。实际上理论家对推进非常丰富类型的函数式编程语言的开发的动机，已经部分地混合了希望带给柯里-霍华德对应更加显著的地位的因素。
_START_SECTION_
类型居留问题
_START_PARAGRAPH_
很明显λ-表达式可以有非常复杂的类型。你可能要问是否有带有给定类型的λ-表达式。找到带有特定类型的λ-表达式的问题叫做类型居留问题。_NEWLINE_答案是非常引人注目的：有带有特定类型的闭合λ-表达式，当且仅当这个类型对应于一个逻辑定理，在这里的→符号再次解释为意味着逻辑蕴涵的时候。_NEWLINE_例如，考虑恒等函数λx.x，它接受类型ξ的参数并返回类型ξ的结果，所以有类型ξ→ξ。ξ→ξ当然是逻辑定理：给定一个公式ξ，你可以结论出ξ。_NEWLINE_K函数的类型α→β→α也是一个定理。如果已知α为真，则你可以结论出如果β为真就能推出α。这有时也叫做重复规则。B的类型是(β→α)→(γ→β)→γ→α。你可类似的把它解释为逻辑重言式；如果已知(β→α)为真，则如果已知(γ→β)为真，你就能推出γ蕴涵α。_NEWLINE_在另一方面，考虑α→β，它不是定理。明显的没有这种类型的λ-项；它必定是接受类型α的参数并返回某个完全无关的和未约束类型的结果的函数。这是不可能的，因为你不能从这种函数里得到什么东西，除非把它放到其他什么地方之中。_NEWLINE_尽管有类型β→(α→α)的函数（比如，λb.λa.a，它接受一个参数b，忽略参数，并返回恒等函数），却没有类型(α→α)→β的函数，如果存在的话，它会是转换恒等函数到任意值的函数。
_START_SECTION_
直觉逻辑
_START_PARAGRAPH_
尽管所有居留类型对应于逻辑定理为真，逆命题却不为真。即使我们限制我们的尝试到只包含→运算的逻辑公式，所谓的逻辑的蕴涵片段，不是所有经典有效的逻辑公式是居留类型。例如，类型((α→β)→α)→α是非居留的，尽管叫做皮尔士定律的对应逻辑公式是重言式。_NEWLINE_直觉逻辑是比经典逻辑弱的系统。经典逻辑把自身关注于在抽象的、柏拉图主义意义上为真的公式，而直觉逻辑只在可以为它构造一个证明的时候认为公式为真。公式α ∨ ¬α示例了这种区别；它是经典逻辑的一个定理而不是直觉逻辑的定理。尽管它是经典的真的，在直觉逻辑中这个公式断言了我们要么证明α要么证明¬α。因为我们不是总能做到这些事情之一，它不是直觉逻辑的一个定理。_NEWLINE_在居留类型和有效逻辑公式之间的对应完全是双向的，如果我们限制我们的注意力到直觉逻辑的蕴涵片段（这也叫做希尔伯特代数）。