Turing completeness of lambda calculus?

Question

How do you argue for the fact that lambda calculus is Turing complete (in the simplest way possible) ?

Horsewhip

You show that all μ-recursive functions can be expressed in the lambda calculus, then rely on the Turing-completeness result for those – Zacynthus

Answer 1

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.

Crosslet

Actually, you have to show that it is possible to implement any Turing machine in the Lambda calculus, or equivalently, a universal Turing machine. – Durkee

Answer 2

Brainfuck is a language that very closely models Turing Machines, and you may find a lambda calculus interpreter spelled out at http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck

Thielen

Implementing a lambda calculus interpreter in a Turing machine doesn't prove anything other than the fact that Turing machines are at least as powerful as the lambda calculus. – Detribalize

If you follow the link above, you'll see that it is a brainfuck interpreter written in (binary) lambda calculus, rather than the reverse that you appear to assume... – Thielen