theory - ラムダ計算のチューリング完全性？

Question

ラムダ計算がチューリング完全であるという事実をどのように主張しますか（可能な限り最も簡単な方法で）？

Answer 1

最も簡単な方法は、ラムダ計算にチューリングマシンを実装することです。ラムダ計算は実質的に高級プログラミング言語であるため、これは非常に簡単です。このアプローチには、他の数学的依存関係を必要としないという利点があります。したがって、引数を提供するための最も簡単な方法を提供する必要があります。

数学的証明の観点から、最短の方法は、µ再帰関数のように、チューリング完全であることがすでに示されている別のパラダイムを実装することです。これらはすでに再帰的に定義されているため、ラムダ計算での表現はチューリングマシン自体よりもわずかにエレガントです。

Answer 2

Brainfuckは、チューリングマシンを非常に厳密にモデル化した言語であり、 http：//en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuckでラムダ計算インタープリターが綴られていることがあります。