मानदंड निर्धारित करने के लिए अगर यह एक प्रोग्रामिंग भाषा

Question

है शर्तों को पूरा करते या बताने के लिए कि एक्स या वाई (या है नहीं) एक प्रोग्रामिंग भाषा है आवश्यक बुनियादी विशेषताएं क्या हैं?

मैं कुछ पढ़ने (Is HTML considered a programming language?, Turing complete, और others) किया है, और निष्कर्ष है कि एक भाषा या एक वाक्य रचना ट्यूरिंग पूरा एक प्रोग्रामिंग भाषा पर विचार किया जाना हो गया है के लिए आया था। क्या ये सही है? यह प्रयाप्त है?

और मैं कैसे निर्धारित करूं कि कुछ ट्यूरिंग है? क्या कोई विशिष्ट मानदंड है?

नियंत्रण-के-प्रवाह संरचनाएं (सशर्त बयान और लूप) को पर विचार करने के लिए पर्याप्त ट्यूरिंग किया जा रहा है?

Answer 1

शब्द "प्रोग्रामिंग भाषा" कुछ हद तक अस्पष्ट है। नियमित अभिव्यक्ति एक प्रोग्रामिंग भाषा का गठन करते हैं? अधिकांश प्रोग्रामर हाँ कहेंगे, भले ही regexes पूर्ण ट्यूरिंग नहीं कर रहे हैं।

ट्यूरिंग-पूर्णता के लिए, मैं कोई विशेषज्ञ नहीं हूं, लेकिन मुझे लगता है कि यह एक सशर्त शाखा और एक अनंत ढेर (इसलिए असली मशीन केवल अनुमानित ट्यूरिंग-पूर्णता) के लिए पर्याप्त है।

संपादित करें: कुछ शोध के बाद, मैंने पाया है कि यह पर्याप्त नहीं है। आपको कम से कम दो ढेर और कुछ न्यूनतम राज्यों (और एक राज्य संक्रमण तालिका) की आवश्यकता है।

शायद एक और डाउन-टू-धरती यार्डस्टिक यह है कि अगर राज्य की मनमानी मात्रा याद हो और लूप्स हो, तो यह शायद पूरा हो रहा है।

Answer 2

प्रोग्रामिंग भाषाएं मौजूद हैं जो ट्यूरिंग पूर्ण नहीं हैं। गैर-ट्यूरिंग पूर्ण भाषाओं के कुछ उदाहरणों के लिए, एक नज़र डालें: Practical non-Turing-complete languages?

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

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

मार्सेलो कहते हैं, यह काफी अस्पष्ट है।

का निर्धारण करने के लिए एक भाषा पूरा ट्यूरिंग रहा है, मैं तुम्हें इस सवाल का उल्लेख करेंगे के लिए के रूप में: What are practical guidelines for evaluating a language's "Turing Completeness"?

Answer 3

क्या शर्तों को पूरा करते या कि एक्स बताने के लिए या Y है आवश्यक बुनियादी विशेषताएं हैं (या नहीं) एक प्रोग्रामिंग भाषा?

मार्सेलो Cantos जैसा कि पहले ही कहा था कि यह कुछ हद तक अस्पष्ट है, विशेष रूप से के बाद से वहाँ डोमेन विशिष्ट भाषाओं (DSLs; http://en.wikipedia.org/wiki/Domain-specific_language) हैं कि पूरा ट्यूरिंग नहीं कर रहे हैं, लेकिन यह भी अक्सर माना जाता प्रोग्रामिंग भाषाओं।

और मैं कैसे निर्धारित करूं कि ट्यूरिंग पूरी हो रही है या नहीं? क्या कोई विशिष्ट मानदंड है?

एक तरीका यह निर्धारित करता है कि एक प्रोग्रामिंग भाषा पूरी तरह से ट्यूरिंग मशीन है (या लैम्ब्डा कैलकुस का कार्यान्वयन) लिखना है।

एक और तरीका साबित करना है कि सभी एमयू-रिकर्सिव फ़ंक्शन http://en.wikipedia.org/wiki/%CE%9C-recursive_function प्रोग्रामिंग भाषा द्वारा गणना की जा सकती है।

चूंकि यह साबित किया जा सकता है कि एक अनिवार्य प्रोग्रामिंग भाषा पूर्ण हो रही है, यदि कोई वैरिएबल असाइनमेंट है, तो संख्या 0 का प्रतिनिधित्व करने का एक तरीका, एक उत्तराधिकारी कार्य, एक पूर्ववर्ती कार्य और समय-समय पर प्रतिनिधित्व करने की संभावना यह है कि यह एक और है मार्ग।

एक कभी-कभी उपयोग किया जाने वाला तरीका (स्पष्ट कारणों पर हमेशा काम नहीं करता है) यह साबित करने के लिए कि एक प्रोग्रामिंग भाषा ट्यूरिंग-पूर्ण नहीं है यह जांचना है कि सभी प्रोग्राम समाप्त हो गए हैं या नहीं; यदि हां, तो यह नहीं हो सकता है।

Answer 4

तो चलो इन ठोस परिभाषा के परिणाम के बारे में सोचते हैं: CSS becomes a programming language:

एक ट्यूरिंग-पूर्ण भाषा एक प्रोग्रामिंग भाषा है।

एक प्रोग्रामिंग भाषा ट्यूरिंग-पूर्ण होना चाहिए: शायद, लेकिन programs can be written otherwise।

अब एक बेहतर बेहतर परिभाषा: एक प्रोग्रामिंग भाषा वह है जिसका उपयोग प्रोग्राम लिखने के लिए किया जा सकता है।