लैम्ब्डा कैलकुस की पूर्णता ट्यूरिंग?

Question

आप इस तथ्य के लिए कैसे बहस करते हैं कि लैम्ब्डा कैलकुलस ट्यूरिंग पूर्ण है (सबसे आसान तरीके से)?

Answer 1

लैम्ब्डा कैलकुस में ट्यूरिंग मशीन को लागू करने का सबसे सरल तरीका है। यह काफी आसान है, क्योंकि लैम्ब्डा कैलकुलस व्यावहारिक रूप से एक उच्च स्तरीय प्रोग्रामिंग भाषा है। इस दृष्टिकोण का कोई अन्य गणितीय निर्भरता की आवश्यकता नहीं है, और इस प्रकार यह आपके तर्क को प्रदान करने का सबसे आसान तरीका प्रदान करना चाहिए।

गणितीय प्रमाण के संदर्भ में, सबसे छोटा तरीका एक और प्रतिमान लागू करके चला जाता है जिसे पहले से ही ट्यूरिंग पूर्ण किया जा रहा है, जैसे μ-recursive कार्यों। ये पहले से ही पुनरावर्ती रूप से परिभाषित हैं, इसलिए लैम्ब्डा कैलकुस में उनकी अभिव्यक्ति ट्यूरिंग मशीन की तुलना में थोड़ा अधिक सुरुचिपूर्ण है।

Answer 2

Brainfuck एक भाषा है कि बहुत बारीकी से मॉडल ट्यूरिंग मशीन, और आप एक लैम्ब्डा पथरी दुभाषिया http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck