Lambda演算的图灵完备性？

Question

14

你如何用最简单的方式证明lambda演算是图灵完备的？

- samsamara

2

你展示了所有的μ-递归函数都可以用λ演算表达，然后依赖于图灵完备性结果。 - Fred Foo

2个回答

1

Brainfuck是一种非常类似于图灵机的语言，您可能会在http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck找到一个λ演算解释器。

- John Tromp

在图灵机中实现λ演算解释器并没有证明任何比图灵机至少与λ演算一样强大的事实。 - chbaker0

如果你点击上面的链接，你会发现这是一个用（二进制）λ演算写成的Brainfuck解释器，而不是你似乎认为的反过来。 - John Tromp

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Weltregierung · Accepted Answer

最直接的方法是在Lambda演算中实现图灵机。这很容易，因为Lambda演算实际上就是一种高级编程语言。这种方法的优点是不需要任何其他数学依赖，因此应该提供了最简单的提供论据的方式。

从数学证明的角度来看，最短的方法是实现另一种已经被证明是图灵完备的范式，例如µ-递归函数。它们已经被递归地定义了，因此它们在Lambda演算中的表达要比图灵机本身更加优美。