कम्प्यूटेबिलिटी

"गणना" redirects here. For अन्य उपयोग, see संगणनीय कार्य. For और, see कम्प्यूटेबिलिटी सिद्धांत. For और, see गणना. For और, see गणना का सिद्धांत. For और, see गणना योग्य संख्या.

कम्प्यूटेबिलिटी समस्या को प्रभावी विधि से समाधान करने की क्षमता है। यह गणितीय तर्क के अंदर संगणनीयता सिद्धांत के क्षेत्र और कंप्यूटर विज्ञान के अंदर संगणना के सिद्धांत का प्रमुख विषय है। किसी समस्या की कम्प्यूटेबिलिटी समस्या का समाधान करने के लिए कलन विधि के अस्तित्व से निकटता से जुड़ी हुई है।

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

समस्याएं

कम्प्यूटेबिलिटी में केंद्रीय विचार (कम्प्यूटेशनल) कम्प्यूटेशनल समस्या का है, जो ऐसा कार्य है जिसकी कम्प्यूटेबिलिटी की जानकारी ज्ञात की जा सकती है।

दो प्रमुख प्रकार की समस्याएं हैं:

• निर्णय समस्या समूह 'S' को ठीक करती है, जो स्ट्रिंग्स, प्राकृतिक संख्याओं या कुछ बड़े समूह 'U' से ली गई अन्य वस्तुओं का समूह हो सकता है। समस्या का विशेष उदाहरण U के एक तत्व U को देखते हुए निर्धारित करना है कि क्या आप S में हैं। उदाहरण के लिए, मान लें कि यू प्राकृतिक संख्याओं का समूह है और S अभाज्य संख्याओं का समूह है। संबंधित निर्णय समस्या प्रारंभिक परीक्षण से मेल खाती है।
• फलन समस्या में समूह "U" से समूह "V" तक फलन "F" होता है। समस्या का उदाहरण U में तत्व u दिए जाने पर, V में संबंधित तत्व f(u) की गणना करना है। उदाहरण के लिए, U और V हो सकते हैं सभी परिमित बाइनरी स्ट्रिंग्स का समुच्चय बनें, और f स्ट्रिंग ले सकता है और इनपुट के अंकों को उलट कर प्राप्त स्ट्रिंग को वापस कर सकता है (इसलिए ए f( 0101) = 1010)।

अन्य प्रकार की समस्याओं में शोध समस्याएँ और अनुकूलन समस्याएँ सम्मिलित हैं।

संगणनीयता सिद्धांत का लक्ष्य यह निर्धारित करना है, कि गणना के प्रत्येक मॉडल में कौन सी समस्याओं या समस्याओं के वर्ग को हल किया जा सकता है।

गणना के औपचारिक मॉडल

Main article: गणना का मॉडल

गणना का मॉडल विशेष प्रकार की कम्प्यूटेशनल प्रक्रिया का औपचारिक विवरण है। विवरण प्रायः एक अमूर्त मशीन का रूप ले लेता है जो कार्य को हाथ में लेने के लिए होता है। ट्यूरिंग मशीन के समतुल्य संगणना के सामान्य मॉडल (चर्च-ट्यूरिंग थीसिस देखें) में सम्मिलित हैं:

लैम्ब्डा कैलकुस: गणना में प्रारंभिक लैम्ब्डा अभिव्यक्ति होती है (या यदि आप फलन और उसके इनपुट को भिन्न करना चाहते हैं तो दो) प्लस लैम्ब्डा नियमो का सीमित अनुक्रम, प्रत्येक बीटा कटौती के आवेदन द्वारा पूर्ववर्ती शब्द से घटाया जाता है।

संयोजनात्मक तर्क

एक अवधारणा जिसमें कई समानताएं हैं $\lambda$-कैलकुलस, किन्तु महत्वपूर्ण अंतर भी उपस्थित हैं (उदाहरण के लिए फिक्स्ड पॉइंट कॉम्बिनेटर वाई का कॉम्बिनेटरी लॉजिक में सामान्य रूप है किन्तु इसमें नहीं $\lambda$-कैलकुलस)। संयोजन तर्क को महान महत्वाकांक्षाओं के साथ विकसित किया गया था: विरोधाभासों की प्रकृति को समझना, गणित की नींव को अधिक आर्थिक (वैचारिक रूप से) बनाना, चर की धारणा को समाप्त करना (इस प्रकार गणित में उनकी भूमिका को स्पष्ट करना)।

μ-पुनरावर्ती कार्य

संगणना में μ-पुनरावर्ती कार्य होता है, अर्थात इसका परिभाषित अनुक्रम, कोई इनपुट मान और इनपुट और आउटपुट के साथ परिभाषित अनुक्रम में दिखाई देने वाले पुनरावर्ती कार्यों का अनुक्रम है। इस प्रकार, यदि पुनरावर्ती फलन f(x) के परिभाषित अनुक्रम में फलन g(x) और h(x,y) दिखाई देते हैं, तब फॉर्म के नियम g(5) = 7 या h(3,2) = 10 के पद प्रकट हो सकते है। इस क्रम में प्रत्येक प्रविष्टि को मूल फलन का अनुप्रयोग होना चाहिए या संरचना (कंप्यूटर विज्ञान), आदिम पुनरावर्तन या रिकर्सन का उपयोग करके उपरोक्त प्रविष्टियों का पालन करना होगा। उदाहरण के लिए यदि f(x) = h(x,g(x)), तो f(5) = 3 प्रकट होने के लिए g(5) = 6 और h(5,6) = 3 जैसे शब्द ऊपर आने चाहिए। गणना तभी समाप्त होती है जब अंतिम पद इनपुट पर प्रारम्भ पुनरावर्ती फलन का मान देता है।

स्ट्रिंग पुनर्लेखन प्रणाली: इसमें मार्कोव एल्गोरिथम सम्मिलित हैं, जो प्रतीकों के स्ट्रिंग (कंप्यूटर विज्ञान) पर काम करने के लिए व्याकरण जैसे नियमों का उपयोग करते हैं; पोस्ट कैनोनिकल सिस्टम भी। रजिस्टर मशीन

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

ट्यूरिंग मशीन: इसके अलावा परिमित राज्य मशीन के समान, सिवाय इसके कि इनपुट एक निष्पादन टेप पर प्रदान किया जाता है, जिसे ट्यूरिंग मशीन पढ़ सकती है, लिख सकती है, या अपने रीड / राइट हेड से आगे और पीछे जा सकती है। टेप को मनमाने आकार में बढ़ने की अनुमति है। ट्यूरिंग मशीन जटिल गणना करने में सक्षम है, जिसकी मनमानी अवधि हो सकती है। यह मॉडल शायद कंप्यूटर विज्ञान में संगणना का सबसे महत्वपूर्ण मॉडल है, क्योंकि यह पूर्वनिर्धारित संसाधन सीमाओं के अभाव में संगणना का अनुकरण करता है। मल्टीटेप ट्यूरिंग मशीन: यहां, एक से अधिक टेप हो सकते हैं; इसके अलावा प्रति टेप कई हेड हो सकते हैं। आश्चर्यजनक रूप से, इस प्रकार की मशीन द्वारा की जा सकने वाली कोई भी संगणना एक साधारण ट्यूरिंग मशीन द्वारा भी की जा सकती है, हालाँकि बाद वाली धीमी हो सकती है या इसके टेप के बड़े कुल क्षेत्र की आवश्यकता होती है।

पी

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

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

गणना के विभिन्न मॉडलों में विभिन्न कार्यों को करने की क्षमता होती है। कम्प्यूटेशनल मॉडल की शक्ति को मापने का एक तरीका औपचारिक भाषाओं की कक्षा का अध्ययन करना है जो मॉडल उत्पन्न कर सकता है; इस प्रकार भाषाओं का चॉम्स्की पदानुक्रम प्राप्त होता है।

संगणना के अन्य प्रतिबंधित मॉडलों में सम्मिलित हैं: नियतात्मक परिमित ऑटोमेटन (DFA): इसे परिमित-अवस्था मशीन भी कहा जाता है। आज अस्तित्व में सभी वास्तविक कंप्यूटिंग उपकरणों को परिमित-राज्य मशीन के रूप में तैयार किया जा सकता है, क्योंकि सभी वास्तविक कंप्यूटर परिमित संसाधनों पर काम करते हैं। इस तरह की मशीन में राज्यों का एक समूह होता है, और राज्य संक्रमणों का एक समूह होता है जो इनपुट स्ट्रीम से प्रभावित होता है। कुछ राज्यों को स्वीकार करने वाले राज्यों के रूप में परिभाषित किया गया है। एक इनपुट स्ट्रीम में फीड किया जाता हैमशीन एक समय में एक वर्ण, और वर्तमान स्थिति के लिए राज्य संक्रमण की तुलना इनपुट स्ट्रीम से की जाती है, और यदि कोई मिलान संक्रमण होता है तो मशीन एक नई स्थिति में प्रवेश कर सकती है। यदि इनपुट स्ट्रीम के अंत में मशीन एक स्वीकार्य स्थिति में है, तो संपूर्ण इनपुट स्ट्रीम स्वीकार की जाती है। गैर नियतात्मक परिमित ऑटोमेटन (NFA): संगणना का एक और सरल मॉडल, हालांकि इसका प्रसंस्करण अनुक्रम विशिष्ट रूप से निर्धारित नहीं है। इसकी व्याख्या राज्यों की सीमित संख्या के माध्यम से एक साथ संगणना के कई रास्तों को लेने के रूप में की जा सकती है। हालांकि, यह साबित करना संभव है कि कोई भी NFA समतुल्य DFA के लिए कम किया जा सकता है। पुशडाउन ऑटोमेटन: परिमित राज्य मशीन के समान, सिवाय इसके कि इसमें एक निष्पादन स्टैक उपलब्ध है, जिसे मनमाने आकार में बढ़ने की अनुमति है। राज्य संक्रमण अतिरिक्त रूप से निर्दिष्ट करता है कि स्टैक में प्रतीक जोड़ना है या स्टैक से प्रतीक को हटाना है। इसकी अनंत-मेमोरी स्टैक के कारण यह DFA से अधिक शक्तिशाली है, हालांकि किसी भी समय केवल स्टैक का शीर्ष तत्व ही एक्सेस किया जा सकता है।

ऑटोमेटा की शक्ति

इन कम्प्यूटेशनल मॉडलों के साथ, हम यह निर्धारित कर सकते हैं कि उनकी सीमाएं क्या हैं। यानी औपचारिक भाषा के कौन से वर्ग वे स्वीकार कर सकते हैं?

परिमित-राज्य मशीनों की शक्ति

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

ऐसी भाषा का एक उदाहरण 'ए' और 'बी' अक्षरों से युक्त सभी स्ट्रिंग्स का समूह है जिसमें अक्षर 'ए' और 'बी' की समान संख्या होती है। यह देखने के लिए कि परिमित राज्य मशीन द्वारा इस भाषा को सही ढंग से क्यों नहीं पहचाना जा सकता है, पहले मान लें कि ऐसी मशीन 'एम' उपस्थित है। एम में कुछ राज्यों की संख्या एन होनी चाहिए। अब 'x' स्ट्रिंग पर विचार करें जिसमें सम्मिलित है $(n+1)$ 'ए' के ​​बाद आता है $(n+1)$ 'बी।

जैसा कि एम एक्स में पढ़ता है, मशीन में कुछ राज्य होना चाहिए जो दोहराए जाते हैं क्योंकि यह 'ए' की पहली श्रृंखला में पढ़ता है, क्योंकि वहां हैं $(n+1)$ 'a's और केवल n कबूतरखाने के सिद्धांत द्वारा बताता है। इस अवस्था को S कहें, और 'a' अनुक्रम के दौरान S की पहली घटना से कुछ बाद की घटना को प्राप्त करने के लिए हमारी मशीन द्वारा पढ़ी जाने वाली 'a' की संख्या को आगे बढ़ने दें। तब हम जानते हैं कि S की दूसरी घटना पर, हम एक अतिरिक्त d जोड़ सकते हैं (जहाँ $d>0$) 'ए' और हम फिर से राज्य एस पर होंगे। इसका मतलब है कि हम जानते हैं कि एक स्ट्रिंग $(n+d+1)$ 'a's को उसी स्थिति में समाप्त होना चाहिए जैसे की स्ट्रिंग $(n+1)$ 'जैसा। इसका तात्पर्य यह है कि यदि हमारी मशीन x को स्वीकार करती है, तो उसे की स्ट्रिंग को भी स्वीकार करना चाहिए $(n+d+1)$ 'ए' के ​​बाद आता है $(n+1)$ 'बी', जो 'ए' और 'बी' की समान संख्या वाली स्ट्रिंग्स की भाषा में नहीं है। दूसरे शब्दों में, एम 'ए' और 'बी' की समान संख्या वाली स्ट्रिंग और एक स्ट्रिंग के बीच सही ढंग से अंतर नहीं कर सकता है $(n+d+1)$ 'के रूप में और $n+1$ 'बी।

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

पुशडाउन ऑटोमेटा की शक्ति

कंप्यूटर वैज्ञानिक एक ऐसी भाषा को परिभाषित करते हैं जिसे एक पुशडाउन ऑटोमेटन द्वारा संदर्भ-मुक्त भाषा के रूप में स्वीकार किया जा सकता है, जिसे संदर्भ-मुक्त व्याकरण के रूप में निर्दिष्ट किया जा सकता है। 'a's और 'b' की समान संख्या वाली स्ट्रिंग वाली भाषा, जिसे हमने दिखाया कि वह एक नियमित भाषा नहीं थी, एक पुश-डाउन ऑटोमेटन द्वारा निर्धारित की जा सकती है। इसके अलावा, सामान्य तौर पर, एक पुश-डाउन ऑटोमेटन एक परिमित-राज्य मशीन की तरह ही व्यवहार कर सकता है, इसलिए यह किसी भी भाषा को निर्धारित कर सकता है जो नियमित है। संगणना का यह मॉडल इस प्रकार परिमित राज्य मशीनों की तुलना में अधिक शक्तिशाली है।

हालाँकि, यह पता चला है कि ऐसी भाषाएँ हैं जिन्हें पुश-डाउन ऑटोमेटन द्वारा भी निर्धारित नहीं किया जा सकता है। परिणाम रेगुलर एक्सप्रेशन के समान है, और यहां विस्तृत नहीं किया जाएगा। संदर्भ-मुक्त भाषाओं के लिए एक पम्पिंग लेम्मा उपस्थित है। ऐसी भाषा का एक उदाहरण अभाज्य संख्याओं का समूह है।

ट्यूरिंग मशीनों की शक्ति

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

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

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

तब पूछने वाला प्रश्न यह है: क्या ऐसी भाषाएँ उपस्थित हैं जो पुनरावर्ती रूप से गणना योग्य हैं, किन्तु पुनरावर्ती नहीं हैं? और, इसके अलावा, क्या ऐसी भाषाएँ हैं जो पुनरावर्ती रूप से गणनीय भी नहीं हैं?

रुकने की समस्या

Main article: Halting problem

हॉल्टिंग समस्या कंप्यूटर विज्ञान की सबसे प्रसिद्ध समस्याओं में से एक है, क्योंकि इसका कम्प्यूटेबिलिटी के सिद्धांत पर गहरा प्रभाव पड़ता है और हम रोजमर्रा के अभ्यास में कंप्यूटर का उपयोग कैसे करते हैं। समस्या को वाक्यांशित किया जा सकता है:

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

यहां हम अभाज्य संख्या या पैलिंड्रोम के बारे में एक साधारण प्रश्न नहीं पूछ रहे हैं, बल्कि हम तालिकाओं को बदल रहे हैं और ट्यूरिंग मशीन से किसी अन्य ट्यूरिंग मशीन के बारे में एक प्रश्न का उत्तर देने के लिए कह रहे हैं। यह दिखाया जा सकता है (मुख्य लेख देखें: हॉल्टिंग प्रॉब्लम) कि ट्यूरिंग मशीन का निर्माण करना संभव नहीं है जो सभी मामलों में इस प्रश्न का उत्तर दे सके।

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

हॉल्टिंग समस्या के एक विस्तार को राइस की प्रमेय कहा जाता है, जिसमें कहा गया है कि यह अनिर्णीत है (सामान्य रूप से) कि दी गई भाषा में कोई विशिष्ट गैर-तुच्छ संपत्ति है या नहीं।

पुनरावर्ती गणना योग्य भाषाओं से परे

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

इस तरह की भाषा का एक सरल उदाहरण हॉल्टिंग भाषा का पूरक है; यह वह भाषा है जिसमें सभी ट्यूरिंग मशीनों को इनपुट स्ट्रिंग्स के साथ जोड़ा जाता है जहाँ ट्यूरिंग मशीनें अपने इनपुट पर नहीं रुकती हैं। यह देखने के लिए कि यह भाषा पुनरावर्ती रूप से गणना योग्य नहीं है, कल्पना करें कि हम एक ट्यूरिंग मशीन M का निर्माण करते हैं जो ऐसी सभी ट्यूरिंग मशीनों के लिए एक निश्चित उत्तर देने में सक्षम है, किन्तु यह किसी भी ट्यूरिंग मशीन पर हमेशा के लिए चल सकती है जो अंततः रुक जाती है। हम फिर एक और ट्यूरिंग मशीन का निर्माण कर सकते हैं $M'$ जो इस मशीन के संचालन का अनुकरण करता है, साथ ही इनपुट में दी गई मशीन के निष्पादन को सीधे सिम्युलेट करने के साथ-साथ दो प्रोग्रामों के निष्पादन को इंटरलीविंग करके। चूंकि प्रत्यक्ष अनुकरण अंततः रुक जाएगा यदि यह अनुकरण करने वाले कार्यक्रम को रोक रहा है, और चूंकि इनपुट कार्यक्रम कभी नहीं रुकेगा, तो धारणा के अनुसार एम का अनुकरण अंततः रुक जाएगा, हम जानते हैं कि $M'$ अंततः इसके समानांतर संस्करणों में से एक पड़ाव होगा। $M'$ इस प्रकार रुकने की समस्या के लिए एक निर्णायक है। हालाँकि, हमने पहले दिखाया है कि रुकने की समस्या अनिर्णीत है। हमारे पास एक विरोधाभास है, और इस प्रकार हमने दिखाया है कि हमारी धारणा है कि एम उपस्थित है गलत है। हॉल्टिंग भाषा का पूरक इसलिए पुनरावर्ती गणना योग्य नहीं है।

समवर्ती-आधारित मॉडल

समांतरता (कंप्यूटर विज्ञान) पर आधारित कई कम्प्यूटेशनल मॉडल विकसित किए गए हैं, जिनमें समानांतर रैंडम-एक्सेस मशीन और पेट्री नेट सम्मिलित हैं। समवर्ती संगणना के ये मॉडल अभी भी किसी भी गणितीय कार्य को प्रारम्भ नहीं करते हैं जिसे ट्यूरिंग मशीनों द्वारा प्रारम्भ नहीं किया जा सकता है।

गणना के मजबूत मॉडल

चर्च-ट्यूरिंग थीसिस का अनुमान है कि कंप्यूटिंग का कोई प्रभावी मॉडल नहीं है जो ट्यूरिंग मशीन की तुलना में अधिक गणितीय कार्यों की गणना कर सके। कंप्यूटर वैज्ञानिकों ने hypercomputer की कई किस्मों की कल्पना की है, कम्प्यूटेशन के मॉडल जो ट्यूरिंग कम्प्यूटेबिलिटी से परे हैं।

अनंत निष्पादन

Main article: Zeno machine

एक ऐसी मशीन की कल्पना करें जहां गणना के प्रत्येक चरण को पिछले चरण के आधे समय की आवश्यकता होती है (और उम्मीद है कि पिछले चरण की आधी ऊर्जा ...) यदि हम पहले चरण के लिए आवश्यक समय की मात्रा को 1/2 समय इकाई (और पहले चरण के लिए आवश्यक ऊर्जा की मात्रा को 1/2 ऊर्जा इकाई ...) तक सामान्य करते हैं, तो निष्पादन की आवश्यकता होगी

$1=\sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots$

समय इकाई (और 1 ऊर्जा इकाई...) चलाने के लिए। यह अनंत श्रृंखला 1 में परिवर्तित हो जाती है, जिसका अर्थ है कि यह ज़ेनो मशीन 1 समय इकाई (1 ऊर्जा इकाई का उपयोग करके ...) में अनगिनत चरणों को निष्पादित कर सकती है। यह मशीन विचाराधीन मशीन के निष्पादन को सीधे अनुकरण करके हॉल्टिंग समस्या का निर्णय करने में सक्षम है। विस्तार से, कोई भी अभिसरण अनंत [साबित रूप से अनंत होना चाहिए] श्रृंखला काम करेगी। यह मानते हुए कि अनंत श्रृंखला एक मूल्य n में परिवर्तित हो जाती है, ज़ेनो मशीन n समय इकाइयों में एक गिनती के अनंत निष्पादन को पूरा करेगी।

ओरेकल मशीनें

Main article: Oracle machine

तथाकथित ओरेकल मशीनों के पास विभिन्न ऑरेकल तक पहुंच है जो विशिष्ट अनिर्णीत समस्याओं का समाधान प्रदान करते हैं। उदाहरण के लिए, ट्यूरिंग मशीन में एक हॉल्टिंग ऑरेकल हो सकता है जो तुरंत उत्तर देता है कि क्या दी गई ट्यूरिंग मशीन किसी दिए गए इनपुट पर कभी रुकेगी। ये मशीनें पुनरावर्तन सिद्धांत में अध्ययन का एक केंद्रीय विषय हैं।

हाइपर-कंप्यूटेशन की सीमाएं

यहां तक ​​कि ये मशीनें, जो प्रतीत होता है कि ऑटोमेटा की उस सीमा का प्रतिनिधित्व करती हैं जिसकी हम कल्पना कर सकते हैं, अपनी सीमाओं में चलती हैं। जबकि उनमें से प्रत्येक एक ट्यूरिंग मशीन के लिए हॉल्टिंग समस्या को हल कर सकता है, वे हॉल्टिंग समस्या के अपने स्वयं के संस्करण को हल नहीं कर सकते। उदाहरण के लिए, Oracle मशीन इस प्रश्न का उत्तर नहीं दे सकती है कि क्या Oracle मशीन कभी रुकेगी या नहीं।

यह भी देखें

• ऑटोमेटा सिद्धांत
• सार मशीन
• अनिर्णीत समस्याओं की सूची
• कम्प्यूटेशनल जटिलता सिद्धांत
• संगणनीयता तर्क

संदर्भ

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Part Two: Computability Theory, Chapters 3–6, pp. 123–222.
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 3: Computability, pp. 57–70.
• S. Barry Cooper (2004). Computability Theory (1st ed.). Chapman & Hall/CRC. ISBN 978-1-58488-237-4.