Product Design, Manufacturing & Innovation Resources
घर » ट्यूरिंग पूर्णता

ट्यूरिंग पूर्णता

1936
  • Alan Turing
कंप्यूटर विज्ञान प्रयोगशाला प्रोग्रामिंग भाषाओं में ट्यूरिंग पूर्णता का प्रदर्शन कर रही है।.

(यह छवि केवल उदाहरण के लिए बनाई गई है)

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

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

किसी सिस्टम के ट्यूरिंग-पूर्ण होने की मुख्य आवश्यकताएं सशर्त शाखाकरण (जैसे, if-then-else कथन) और अनिश्चित काल तक या पुनरावर्ती रूप से लूप करने की क्षमता (जैसे, while और for लूप) हैं। ये संरचनाएं सिस्टम को निर्णय लेने और संचालन दोहराने की अनुमति देती हैं, जो ट्यूरिंग मशीन के स्टेट ट्रांजिशन और टेप हेरफेर के व्यवहार को मॉडल करने के लिए पर्याप्त है। चर्च-ट्यूरिंग थीसिस, कंप्यूटर विज्ञान का एक मूलभूत सिद्धांत, यह मानता है कि कोई भी फ़ंक्शन जिसे स्वाभाविक रूप से "गणना योग्य" माना जाता है, उसे ट्यूरिंग मशीन द्वारा गणना किया जा सकता है। इसलिए, सैद्धांतिक रूप से, एक ट्यूरिंग-पूर्ण भाषा किसी भी एल्गोरिदम को व्यक्त करने में सक्षम है।

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

UNESCO Nomenclature: 1202
कंप्यूटर विज्ञान

Type

सार प्रणाली

व्यवधान

इंक्रीमेंटल

उपयोग

व्यापक उपयोग

शगुन

  • Kurt Gödel’s work on incompleteness theorems
  • अलोंजो चर्च द्वारा लैम्डा कैलकुलस का विकास
  • गणित को औपचारिक रूप देने के लिए डेविड हिल्बर्ट का कार्यक्रम
  • एल्गोरिदम की अवधारणा प्राचीन काल से चली आ रही है।

आवेदन

  • सामान्य प्रयोजन वाली प्रोग्रामिंग भाषाएँ (पायथन, सी++, जावा)
  • मैक्रो क्षमताओं वाले स्प्रेडशीट सिस्टम (उदाहरण के लिए, वीबीए के साथ एक्सेल)
  • माइनक्राफ्ट का रेडस्टोन सर्किट
  • cellular automata like conway’s game of life
  • रिकर्सिव कॉमन टेबल एक्सप्रेशंस के साथ कुछ उन्नत SQL एक्सटेंशन
  • सी++ टेम्पलेट मेटाप्रोग्रामिंग सबसिस्टम
  • कुछ HTML संयोजनों के साथ CSS3

पेटेंट:

NA

संभावित नवाचार विचार

बॉट ट्रैफिक को कम करने के कारण, जो वर्तमान में प्रति दिन 40,000 से अधिक है, यह सामग्री केवल समुदाय के सदस्यों के लिए आरक्षित है।
> लॉगिन < या > रजिस्टर < इस सामग्री और अन्य सभी प्रतिबंधित सामग्रियों और उपकरणों तक पहुंच (100% निःशुल्क) है।

संबंधित विषय: ट्यूरिंग पूर्णता, ट्यूरिंग मशीन, गणनात्मकता सिद्धांत, एलन ट्यूरिंग, चर्च-ट्यूरिंग थीसिस, सार्वभौमिक गणना, एल्गोरिदम, औपचारिक भाषा, निर्णयशीलता, हॉल्टिंग समस्या।

ऐतिहासिक संदर्भ

ट्यूरिंग पूर्णता

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

(यदि तिथि अज्ञात है या प्रासंगिक नहीं है, उदाहरण के लिए "द्रव यांत्रिकी", तो इसके उल्लेखनीय उद्भव का एक अनुमानित आंकड़ा प्रदान किया गया है)

संबंधित आविष्कार, नवाचार और तकनीकी सिद्धांत

पंजीकृत सदस्यों के लिए पूर्ण आकार की छवियाँ और डाउनलोड 100% निःशुल्क उपलब्ध हैं।