تورينج اكتمال حساب التفاضل والتكامل Lambda؟

Question

كيف تجادل لحقيقة أن حساب التفاضل والتكامل Lambda هو تورينج كاملة (في أبسط طريقة ممكنة)؟

Answer 1

الطريقة الأكثر وضوحا هي تطبيق آلة Turing في حساب التفاضل والتكامل Lambda.هذا سهل للغاية، لأن حساب التفاضل والتكامل Lambda عمليا لغة برمجة عالية المستوى.هذا النهج لديه ميزة عدم مطالبة أي تبعيات رياضية أخرى، وبالتالي ينبغي أن توفر أبسط طريقة ممكنة لتوفير حجتك.

فيما يتعلق بإثبات رياضي، فإن أقصر طريقة تنفذ نموذجا آخر قد أظهرت بالفعل أن تورينج كاملا، مثل وظائف μ-Recursive.يتم تحديدها بالفعل بشكل متكرر، لذلك تعبيرها في حساب التفاضل والتكامل Lambda أناقة أكثر قليلا من آلة Turing نفسها.

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