Turing completeness of lambda calculus?

你如何认为lambda微积分是图灵完备的（尽可能以最简单的方式）？

---

The most straightforward way is to implement a Turing Machine in the Lambda Calculus. This is quite easy, because the Lambda Calculus is practically a high level programming language. This approach has the advantage of not requiring any other mathematical dependencies, and it should thus provide the simplest possible way of providing your argument.

In terms of a mathematical proof, the shortest way goes by implementing another paradigm that has already been shown to be Turing complete, like µ-recursive functions. These are already recursively defined, so their expression in the Lambda calculus is slightly more elegant than the Turing Machine itself.

---

Brainfuck是一种非常接近Turing Machines的语言，你可以在http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck找到一个lambda演算解释器。

链接地址: http://www.djcxy.com/p/67868.html

上一篇: Brainfuck Hello World实际上如何工作？

下一篇: lambda演算的图灵完备性？