Turing đầy đủ tính toán lambda?

Question

Làm thế nào để bạn tranh luận cho thực tế là tính toán lambda là Turing hoàn thành (theo cách đơn giản nhất có thể)?

Answer 1

Cách đơn giản nhất là triển khai Máy Turing trong Phép tính Lambda. Điều này là khá dễ dàng, bởi vì Lambda Calculus thực tế là một ngôn ngữ lập trình bậc cao. Cách tiếp cận này có lợi thế là không yêu cầu bất kỳ phụ thuộc toán học nào khác, và do đó nó sẽ cung cấp cách đơn giản nhất có thể để cung cấp đối số của bạn.

Xét về mặt toán học, cách ngắn nhất bằng cách thực hiện một mô hình khác đã được chứng minh là Turing hoàn chỉnh, giống như các hàm đệ quy.. Chúng đã được định nghĩa đệ quy, vì vậy biểu thức của chúng trong phép tính Lambda là thanh lịch hơn một chút so với bản thân máy Turing.

Answer 2

Brainfuck là một ngôn ngữ mà mô hình rất chặt chẽ Turing Máy móc, và bạn có thể tìm thấy một thông dịch viên lambda calculus nêu ra tại http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck