gpt4 book ai didi

encoding - Binary Lambda Calculus 如何编码括号?

转载 作者:行者123 更新时间:2023-12-04 14:14:14 24 4
gpt4 key购买 nike

BLC 如何编码括号?例如,这将如何:

λa.λb.λc.(a ((b c) d))

用 BLC 编码?

注意:维基百科的文章不是很有帮助,因为它使用了一种不熟悉的符号,并且只提供了一个不涉及括号的简单示例,以及一个很难分析的非常复杂的示例。这篇论文在这方面是相似的。

最佳答案

如果您指的是基于 Wikipedia 中讨论的 De Bruijn 索引的二进制编码,那实际上非常简单。您首先需要进行 De Bruijn 编码,这意味着用自然数替换变量,表示变量与其 λ 绑定(bind)器之间的 λ 绑定(bind)器的数量。在这个符号中,

λa.λb.λc.(a ((b c) d))

变成
λλλ 3 ((2 1) d)

其中 d 是某个自然数 >=4。由于它在表达式中是未绑定(bind)的,因此我们无法真正判断它应该是哪个数字。

然后编码本身,递归定义为
enc(λM) = 00 + enc(M)
enc(MN) = 01 + enc(M) + enc(N)
enc(i) = 1*i + 0

在哪里 +表示字符串连接,* 表示重复。系统地应用这个,我们得到
  enc(λλλ 3 ((2 1) d))
= 00 + enc(λλ 3 ((2 1) d))
= 00 + 00 + enc(λ 3 ((2 1) d))
= 00 + 00 + 00 + enc(3 ((2 1) d))
= 00 + 00 + 00 + 01 + enc(3) + enc((2 1) d)
= 00 + 00 + 00 + 01 + enc(3) + 01 + enc(2 1) + enc(d)
= 00 + 00 + 00 + 01 + enc(3) + 01 + 01 + enc(2) + enc(1) + enc(d)
= 000000011110010111010 + enc(d)

如您所见,开括号被编码为 01而在此编码中不需要关闭括号。

关于encoding - Binary Lambda Calculus 如何编码括号?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18034246/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com