Turing completeness of lambda calculus?

Question

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

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.

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