你如何论证 lambda 演算是图灵完备的（以最简单的方式）？
问问题
3741 次
2 回答
9
最直接的方法是在 Lambda 演算中实现图灵机。这很容易，因为 Lambda 演算实际上是一种高级编程语言。这种方法的优点是不需要任何其他数学依赖，因此它应该提供最简单的方法来提供你的论点。
就数学证明而言，最短的方法是实现另一个已经被证明是图灵完备的范式，比如 µ 递归函数。这些已经被递归定义了，所以它们在 Lambda 演算中的表达比图灵机本身要优雅一些。
于 2012-05-09T21:11:01.127 回答
1
Brainfuck 是一种非常接近图灵机模型的语言，您可以在 http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck找到一个 lambda 演算解释器
于 2013-08-31T02:23:02.277 回答