क्या कोई भाषा सरणी के लिए किसी भी समर्थन के बिना ट्यूरिंग-पूर्ण हो सकती है?

Question

यदि किसी भाषा में नियंत्रण संरचनाएं और चर होते हैं, लेकिन सरणी, सूचियों, स्मृति पहुंच और आवंटन आदि के लिए कोई समर्थन नहीं है, तो क्या यह ट्यूरिंग-पूर्ण हो सकता है?

हो सकता है कि अगर वहाँ चर आप बना सकते हैं की राशि की कोई सीमा नहीं था, तो आप सरणियों उन के माध्यम से की तरह array_1, array_2, ... array_6000 और मैन्युअल रूप से पाश चर बनाने के द्वारा अनुकरण कर सकते हैं, और किसी भी तरह जटिल डेटा संरचनाओं और प्रत्यावर्तन बनाने?

संपादित करें: भले ही आप नाम मैनिपुलेशन (array_10+i की अनुमति नहीं है) द्वारा चर का उपयोग नहीं कर सकते हैं?

Answer 1

निश्चित रूप से। Lambda Calculus पर एक नज़र डालें, जो मैंने कभी देखा है सबसे कम ट्यूरिंग पूर्ण भाषाओं में से एक है। असल में, आपके पास सभी हैं lambdas (फ़ंक्शन अक्षर); कोई असाइनमेंट नहीं, कोई घोषणा नहीं, कोई डेटा संरचना नहीं। यह सब बहुत पतला हो गया है।

हालांकि, आप एक सूची की तरह एक रेखीय डेटा संरचना कार्यों को एक साथ चेनिंग द्वारा अनुकरण कर सकते हैं। यह बहुत verbose हो जाता है, लेकिन यह निश्चित रूप से संभव है और अनुक्रमिक रूप से नामित चर की एक बड़ी श्रृंखला होने की तुलना में यह बहुत अच्छा है।

सामान्य शब्दों में, या नहीं, एक भाषा ट्यूरिंग पूरा चाहे वह सरणी के साथ कोई संबंध नहीं है है। एसएमएल और हास्केल जैसी कार्यात्मक भाषाओं में लम्बा कैलकुस की तरह सरणी की कमी है, और ये वास्तव में उपयोगी भाषाएं हैं! एक भाषा कहकर "ट्यूरिंग पूर्ण" यह कहने का एक और तरीका है कि कोई ट्यूरिंग कम्प्यूटेबल फ़ंक्शन नहीं है जिसे कहा गया भाषा में व्यक्त नहीं किया जा सकता है। यह एक आश्चर्यजनक रूप से ढीला योग्यता है, जो कई भाषाओं को अनुमति देता है जो पूरी तरह से अव्यवहारिक (लैम्ब्डा कैलकुस की तरह) होंगे।

Answer 2

वहाँ ट्यूरिंग-पूर्ण भाषाओं के बहुत सारे है कि एक "चर" की धारणा नहीं है है! मेमोरी एक्सेस और आवंटन कार्यान्वयन विवरण हैं, इसलिए वे पूरी तरह से अप्रासंगिक हैं। आपको यह समझना होगा कि ट्यूरिंग मशीन और ट्यूरिंग पूर्णता बहुत सैद्धांतिक अवधारणाएं हैं, जो चीजों को साबित करने के लिए उपयोगी हैं, लेकिन वास्तविक हार्डवेयर की वास्तविकता से पूरी तरह से तलाकशुदा हैं।

पॉल ग्राहम एक लंबी लिखा है, लेकिन बहुत, बहुत ही दिलचस्प essay कंप्यूटर भाषाओं के इतिहास जहां वह कंप्यूटर भाषाओं के दो बहुत अलग मुख्य परंपराओं का वर्णन करता है पर:

• लिस्प, योजना, आदि - व्युत्पन्न सैद्धांतिक विचारों, बहुत ही सरल, अभी तक धारणात्मक शक्तिशाली भाषाओं से है, लेकिन लंबे समय तक क्या आसान और सक्षम के लिए उनकी पूरी उपेक्षा की वजह से अव्यावहारिक समय लागू करने के लिए
• असेंबलर, FORTRAN, सी और काफी सब "मुख्यधारा" भाषाओं के लिए - प्राप्त होने वाले अधिक या हार्डवेयर क्या कर सकता है, लागू करने में आसान, कुशल, लेकिन इसके लिए सीधे से कम अभिव्यक्ति के मामले में सबसे पुराना समय (पुराना!) लिस्प परिवार।

ऐसा लगता है कि आप केवल दूसरी परंपरा को जानते हैं, लेकिन ट्यूरिंग पूर्णता एक अवधारणा है जो पहली परंपरा के समान सिद्धांतों से उत्पन्न होती है और यदि आप उन सिद्धांतों को नहीं जानते हैं तो थोड़ा समझ में आता है।