邱奇数 Church encoding
(重定向自Church integer)
邱奇编码是把数据和运算符嵌入到lambda演算内的一种方式,最常见的形式是邱奇数,它是使用lambda符号的自然数的表示法。这种方法得名于阿隆佐·邱奇,他首先以这种方法把数据编码到lambda演算中。
在其他符号系统中通常被认定为基本的项(比如整数、布尔值、有序对、列表和tagged unions)都被映射到使用 邱奇编码的高阶函数;根据邱奇-图灵论题我们知道任何可计算的运算符(和它的运算数)都可以用邱奇编码表示。
很多学数学的学生熟悉可计算函数集合的哥德尔编号;邱奇编码是定义在lambda抽象而不是自然数上的等价运算。