3

关于 lambda 演算的维基百科条目定义了一些适用于教堂数字的公式,例如

SUCC := λn.λf.λx.f (n f x)

在 Churches 论文中,他首先定义了他的 lambda 演算,他说

..两个变量的函数,当采用格式良好的公式 F 和 X 时,其值为公式{F}(X),是递归的。

后来在他的论文中,他称这个函数为B(m,n)

如何使用所有这些信息来描述类似的功能如何BSUCC 1

我知道我们将不得不将输入和输出计算为素数的幂,因为他在整篇论文中都使用了哥德尔的编号系统,但是我发现很难将它们拼凑在一起。

4

1 回答 1

0

我将 lambda 演算与 javascript 一起使用。我将尝试展示一些小例子,以及Bluebird/ComposeSUCC函数是如何工作的,并且可以组合使用。B

首先提醒一下Church-Numerals(在 JS 中):

const n0 = f => x => x       
const n1 = f => x => f(x) 
const n2 = f => x => f(f(x))     
const n3 = f => x => f(f(f(x)))

以及 SUCC := λnfx.f(nfx)JS 中教堂数字的继任者: const succ = n => f => x => f( n(f)(x) ). 我们可以看到succ-Function 只需要一个 Church-Numeral 并在f前面添加一个,因此succ(n1)带有主体的 af(x)将是f(f(x))。因此,它最终f总共做了 1 + n 个组合。

// example creating new Church-Numbers with the Succesor-Function
const n4 = succ(n3)
const n5 = succ(n4)

// or do Addition with Church-Numbers
const n7  = n2(succ)(n5)
const n10 = n5(succ)(n5)

//to test if it works, us the helper-function churchtoJsNum
const churchtoJsNum = n => n(x => x + 1)(0)

churchtoJsNum(n10) // 10

还有另一种写后继的方法,因为我们正在做 n-fold 组合:组合函数。BSmullyan 在 Curry 的组合器之后将其命名为 Bluebird 。

B := λfgx.f(gx)

在 JS 中:const B = f => g => x => f(g(x))

现在可以结合succB-Function。

const succ = n => f => x => B(f) (n(f)) (x)  

现在我们有了一个实际的组合函数,我们可以在不提及最终 x 值参数的情况下定义后继。

const succ = n => f => B(f)(n(f));

于 2021-03-03T23:09:35.433 回答