14

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

Michael0x2a
  • 58,192
  • 30
  • 175
  • 224
samsamara
  • 4,630
  • 7
  • 36
  • 66
  • 2
    You show that all [μ-recursive functions](https://en.wikipedia.org/wiki/%CE%9C-recursive_function) can be expressed in the lambda calculus, then rely on the Turing-completeness result for those – Fred Foo Mar 08 '12 at 14:31

2 Answers2

9

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.

Weltregierung
  • 206
  • 3
  • 3
1

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

John Tromp
  • 274
  • 2
  • 3
  • 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. – chbaker0 Apr 26 '18 at 18:30
  • 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... – John Tromp Apr 28 '18 at 04:33