हाइपरकंप्यूटेशन: Difference between revisions
(→इतिहास) |
(→इतिहास) |
||
Line 7: | Line 7: | ||
==इतिहास== | ==इतिहास== | ||
ट्यूरिंग मशीनों से आगे जाने वाला एक कम्प्यूटेशनल मॉडल [[एलन ट्यूरिंग]] द्वारा अपने 1938 के पीएचडी शोध प्रबंध [[ऑर्डिनल्स पर आधारित तर्क की प्रणालियाँ|"सिस्टम्स ऑफ़ लॉजिक बेस्ड ऑन ऑर्डिनल्स"]] में प्रस्तुत किया गया था।<ref>{{Cite journal |doi = 10.1112/plms/s2-45.1.161|title = Systems of Logic Based on Ordinals†|year = 1939|last1 = Turing|first1 = A. M.|journal = Proceedings of the London Mathematical Society|volume = 45|pages = 161–228|hdl = 21.11116/0000-0001-91CE-3|hdl-access=free}}</ref> | ट्यूरिंग मशीनों से आगे जाने वाला एक कम्प्यूटेशनल मॉडल [[एलन ट्यूरिंग]] द्वारा अपने 1938 के पीएचडी शोध प्रबंध [[ऑर्डिनल्स पर आधारित तर्क की प्रणालियाँ|"सिस्टम्स ऑफ़ लॉजिक बेस्ड ऑन ऑर्डिनल्स"]] में प्रस्तुत किया गया था।<ref>{{Cite journal |doi = 10.1112/plms/s2-45.1.161|title = Systems of Logic Based on Ordinals†|year = 1939|last1 = Turing|first1 = A. M.|journal = Proceedings of the London Mathematical Society|volume = 45|pages = 161–228|hdl = 21.11116/0000-0001-91CE-3|hdl-access=free}}</ref> इस लेख में ऐसे गणितीय प्रणालियों की खोज की गई, जिनमें [[ओरेकल मशीन|ओरेकल]] उपलब्ध था, जो प्राकृतिक संख्याओं से [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]] के लिए एक गैर-पुनरावृत्ति विशेष फलन की गणना कर सकता था। उन्होंने इस उपकरण का उपयोग यह सिद्ध करने के लिए किया कि उन अधिक शक्तिशाली प्रणालियों में भी, [[अनिर्णीत समस्या|अपरिभाष्यता समस्या]] अभी भी उपलब्ध है। ट्यूरिंग के ऑरेकल मशीन गणितीय अवकलन हैं और इन्हें भौतिक रूप से संभाव्य नहीं बनाया जा सकता है।<ref>"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper ''Systems of Logic Based On Ordinals'')</ref> | ||
इस लेख में ऐसे गणितीय प्रणालियों की खोज की गई, जिनमें [[ओरेकल मशीन|ओरेकल]] उपलब्ध था, जो प्राकृतिक संख्याओं से [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]] के लिए एक गैर-पुनरावृत्ति विशेष फलन की गणना कर सकता था। उन्होंने इस उपकरण का उपयोग यह सिद्ध करने के लिए किया कि उन अधिक शक्तिशाली प्रणालियों में भी, [[अनिर्णीत समस्या|अपरिभाष्यता समस्या]] अभी भी उपलब्ध है। ट्यूरिंग के ऑरेकल मशीन गणितीय अवकलन हैं और इन्हें भौतिक रूप से संभाव्य नहीं बनाया जा सकता है।<ref>"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper ''Systems of Logic Based On Ordinals'')</ref> | |||
==राज्य स्थान== | ==राज्य स्थान== |
Revision as of 23:19, 25 July 2023
हाइपरकंप्यूटेशन या सुपर-ट्यूरिंग कंप्यूटेशन, कंप्यूटेशनल मॉडलों का एक सेट है जो ऐसे आउटपुट प्रदान कर सकता है जो ट्यूरिंग-कम्प्यूटेबल नहीं हैं। सुपर-ट्यूरिंग कंप्यूटिंग, जिसे 1990 के दशक के प्रारंभ में हावा सीगलमैन द्वारा प्रस्तुत किया गया था, ऐसे न्यूरोलॉजिकल प्रेरित, जैविक और भौतिक कंप्यूटिंग को संदर्भित करता है; यह लाइफलॉंग मशीन लर्निंग का गणितीय आधार बन गया। हाइपरकंप्यूटेशन, जिसे 1990 के दशक के अंत में विज्ञान के एक क्षेत्र के रूप में प्रस्तुत किया गया था, कहा जाता है कि यह सुपर-ट्यूरिंग पर आधारित है, परंतु इसमें ऐसे निर्माण भी सम्मिलित हैं जो दार्शनिक हैं। उदाहरण के लिए, एक मशीन जो हॉल्टिंग प्रॉब्लम का समाधान कर सकती है वह हाइपर कंप्यूटर होगी; इसी प्रकार वह मशीन भी हाइपरकंप्यूटर होगी जो पीनो अंकगणित में प्रत्येक कथन का सही समाधान कर सकती है।
चर्च-ट्यूरिंग थीसिस में कहा गया है कि किसी भी ''गणनीय'' फलन की गणना, यदि किसी गणितज्ञ द्वारा सरल विधिकलन के किसी परिमित समुच्चय का उपयोग करके कलम और कागज के साथ की जा सकती है, तो ट्यूरिंग मशीन द्वारा भी इसकी गणना की जा सकती है। हाइपरकंप्यूटर उन फलनों की गणना करता है जो एक ट्यूरिंग मशीन नहीं कर सकती है और जो, इस प्रकार चर्च-ट्यूरिंग अर्थ में "गणनीय" नहीं हैं।
तकनीकी रूप से, एक रैंडम ट्यूरिंग मशीन का आउटपुट गणनीय नहीं है; यद्यपि, अधिकांश हाइपरकंप्यूटिंग साहित्य, यादृच्छिक, अगणनीय फलनों के अतिरिक्त, निर्धारणात्मक फलनों की गणना पर ध्यान केंद्रित करता है।
इतिहास
ट्यूरिंग मशीनों से आगे जाने वाला एक कम्प्यूटेशनल मॉडल एलन ट्यूरिंग द्वारा अपने 1938 के पीएचडी शोध प्रबंध "सिस्टम्स ऑफ़ लॉजिक बेस्ड ऑन ऑर्डिनल्स" में प्रस्तुत किया गया था।[1] इस लेख में ऐसे गणितीय प्रणालियों की खोज की गई, जिनमें ओरेकल उपलब्ध था, जो प्राकृतिक संख्याओं से प्राकृतिक संख्याओं के लिए एक गैर-पुनरावृत्ति विशेष फलन की गणना कर सकता था। उन्होंने इस उपकरण का उपयोग यह सिद्ध करने के लिए किया कि उन अधिक शक्तिशाली प्रणालियों में भी, अपरिभाष्यता समस्या अभी भी उपलब्ध है। ट्यूरिंग के ऑरेकल मशीन गणितीय अवकलन हैं और इन्हें भौतिक रूप से संभाव्य नहीं बनाया जा सकता है।[2]
राज्य स्थान
एक अर्थ में, अधिकांश फ़ंक्शन अप्राप्य हैं: एलेफ़ 0|गणनीय कार्य, परंतु एक बेशुमार संख्या है () संभावित सुपर-ट्यूरिंग फ़ंक्शंस।[3]
मॉडल
हाइपरकंप्यूटर मॉडल उपयोगी परंतु संभवतः अवास्तविक (जैसे कि ट्यूरिंग की मूल ओरेकल मशीनें) से लेकर, कम-उपयोगी यादृच्छिक-फ़ंक्शन जेनरेटर तक होते हैं जो अधिक प्रशंसनीय रूप से व्यवहार्य होते हैं (जैसे कि यादृच्छिक ट्यूरिंग मशीन)।
अगणनीय इनपुट या ब्लैक-बॉक्स घटक
एक प्रणाली ने एक इनपुट के रूप में अगणनीय, अलौकिक चैतिन स्थिरांक (अंकों के अनंत अनुक्रम वाली एक संख्या जो रुकने की समस्या के समाधान को कूटबद्ध करती है) का ज्ञान प्रदान किया है, जो बड़ी संख्या में उपयोगी अनिर्णीत समस्याओं को हल कर सकता है; एक इनपुट के रूप में एक अगणनीय यादृच्छिक-संख्या जनरेटर प्रदान किया गया सिस्टम यादृच्छिक अगणनीय कार्यों का निर्माण कर सकता है, परंतु आम तौर पर यह नहीं माना जाता है कि यह हॉल्टिंग समस्या जैसे उपयोगी अगणनीय कार्यों को सार्थक रूप से हल करने में सक्षम है। विभिन्न प्रकार के कल्पनीय हाइपरकंप्यूटरों की असीमित संख्या है, जिनमें सम्मिलित हैं:
- ट्यूरिंग की मूल ओरेकल मशीनें, 1939 में ट्यूरिंग द्वारा परिभाषित।
- एक वास्तविक कंप्यूटर (एक प्रकार का आदर्श एनालॉग कंप्यूटर) हाइपरकंप्यूटेशन कर सकता है[4] यदि भौतिकी सामान्य वास्तविक संख्या चर (केवल गणनीय संख्या नहीं) को स्वीकार करती है, और ये किसी तरह से उपयोगी (यादृच्छिक के बजाय) गणना के लिए उपयोगी हैं। इसके लिए भौतिकी के काफी विचित्र नियमों की आवश्यकता हो सकती है (उदाहरण के लिए, एक अलौकिक मूल्य के साथ मापने योग्य भौतिक स्थिरांक, जैसे कि चैतिन का स्थिरांक), और वास्तविक-मूल्यवान भौतिक मूल्य को मनमाने ढंग से परिशुद्धता में मापने की क्षमता की आवश्यकता होगी, हालांकि मानक भौतिकी ऐसे मनमाने-सटीक माप को सैद्धांतिक रूप से अव्यवहार्य बनाती है।[5]
- इसी तरह, एक तंत्रिका जाल जिसमें चैतिन का स्थिरांक किसी तरह उसके वजन फ़ंक्शन में सटीक रूप से अंतर्निहित होता है, रुकने की समस्या को हल करने में सक्षम होगा,[6] परंतु यह वास्तविक गणना पर आधारित हाइपरकंप्यूटेशन के अन्य मॉडलों की तरह ही भौतिक कठिनाइयों के अधीन है।
- कुछ फ़ज़ी लॉजिक-आधारित फ़ज़ी ट्यूरिंग मशीनें, परिभाषा के अनुसार, गलती से रुकने की समस्या को हल कर सकती हैं, परंतु केवल इसलिए क्योंकि रुकने की समस्या को हल करने की उनकी क्षमता परोक्ष रूप से मशीन के विनिर्देशन में मानी जाती है; इसे मशीनों के मूल विनिर्देश में एक बग के रूप में देखा जाता है।[7][8]
- इसी तरह, एक प्रस्तावित मॉडल जिसे निष्पक्ष गैर-नियतिवाद के रूप में जाना जाता है, गलती से गैर-गणनीय कार्यों की मौखिक गणना की अनुमति दे सकता है, क्योंकि परिभाषा के अनुसार, ऐसी कुछ प्रणालियों में अस्वीकार इनपुट की पहचान करने की मौखिक क्षमता होती है जो गलत तरीके से एक उपप्रणाली को हमेशा के लिए चलाने का कारण बनेगी।[9][10]
- दिमित्रो तारानोव्स्की ने विश्लेषण की पारंपरिक रूप से गैर-फ़िनिटिस्टिक शाखाओं का एक परिमितवाद मॉडल प्रस्तावित किया है, जो एक ट्यूरिंग मशीन के आसपास बनाया गया है जो इसके ओरेकल के रूप में तेजी से बढ़ते फ़ंक्शन से सुसज्जित है। इस और अधिक जटिल मॉडलों के द्वारा वह दूसरे क्रम के अंकगणित की व्याख्या देने में सक्षम थे। इन मॉडलों को एक अगणनीय इनपुट की आवश्यकता होती है, जैसे कि एक भौतिक घटना-उत्पादन प्रक्रिया जहां घटनाओं के बीच का अंतराल एक अगणनीय रूप से बड़ी दर से बढ़ता है।[11]
- इसी तरह, असीमित गैर-नियतिवाद के मॉडल की एक अपरंपरागत व्याख्या, परिभाषा के अनुसार, यह मानती है कि एक अभिनेता को व्यवस्थित होने के लिए आवश्यक समय की अवधि मौलिक रूप से अज्ञात है, और इसलिए मॉडल के भीतर यह सिद्ध नहीं किया जा सकता है कि इसमें कोई समय नहीं लगता है। समय की निर्विवाद रूप से लंबी अवधि।[12]
अनंत कम्प्यूटेशनल चरण मॉडल
सही ढंग से काम करने के लिए, नीचे दी गई मशीनों द्वारा कुछ गणनाओं के लिए वस्तुतः असीमित परंतु सीमित, भौतिक स्थान और संसाधनों के बजाय अनंत की आवश्यकता होती है; इसके विपरीत, ट्यूरिंग मशीन के साथ, किसी भी गणना को रोकने के लिए केवल सीमित भौतिक स्थान और संसाधनों की आवश्यकता होगी।
- एक ट्यूरिंग मशीन जो सीमित समय में अनगिनत चरणों को पूरा कर सकती है, एक उपलब्धि जिसे सुपरटास्क के रूप में जाना जाता है। केवल असीमित संख्या में कदम चलने में सक्षम होना ही पर्याप्त नहीं है। एक गणितीय मॉडल ज़ेनो मशीन है (ज़ेनो के विरोधाभास से प्रेरित)। ज़ेनो मशीन अपना पहला संगणना चरण (मान लीजिए) 1 मिनट में, दूसरा चरण ½ मिनट में, तीसरा चरण ¼ मिनट में, आदि पूरा करती है। 1/2 + 1/4 + 1/8 + 1/16 + ⋯ का योग करके |1+½+¼+... (एक ज्यामितीय श्रृंखला) हम देखते हैं कि मशीन कुल 2 मिनट में अनंत रूप से कई चरण पूरा करती है। शग्रीर के अनुसार, ज़ेनो मशीनें भौतिक विरोधाभास प्रस्तुत करती हैं और इसकी स्थिति [0, 2) की एक तरफ की खुली अवधि के बाहर तार्किक रूप से अपरिभाषित है, इस प्रकार गणना के प्रारंभ के ठीक 2 मिनट बाद अपरिभाषित है।[13]
- यह स्वाभाविक लगता है कि समय यात्रा की संभावना (बंद टाइमलाइक कर्व्स (सीटीसी) का अस्तित्व) हाइपरकंप्यूटेशन को अपने आप संभव बनाती है। यद्यपि, ऐसा नहीं है क्योंकि सीटीसी (स्वयं) असीमित मात्रा में भंडारण प्रदान नहीं करता है जिसकी अनंत गणना के लिए आवश्यकता होगी। फिर भी, ऐसे स्पेसटाइम हैं जिनमें सीटीसी क्षेत्र का उपयोग सापेक्षतावादी हाइपरकंप्यूटेशन के लिए किया जा सकता है।[14] 1992 के एक पेपर के अनुसार,[15] एक कंप्यूटर जो मैलामेंट-होगर्थ स्पेसटाइम में या घूमते हुए ब्लैक होल के चारों ओर कक्षा में काम कर रहा है[16] सैद्धांतिक रूप से ब्लैक होल के अंदर एक पर्यवेक्षक के लिए गैर-ट्यूरिंग गणना कर सकता है।[17][18] सीटीसी तक पहुंच पीएसपीएसीई-पूर्ण समस्याओं के त्वरित समाधान की अनुमति दे सकती है, एक जटिलता वर्ग, जो ट्यूरिंग-निर्णायक होने के बावजूद, आमतौर पर कम्प्यूटेशनल रूप से कठिन माना जाता है।[19][20]
क्वांटम मॉडल
कुछ विद्वानों का अनुमान है कि एक क्वांटम यांत्रिकी प्रणाली जो किसी तरह राज्यों के अनंत सुपरपोजिशन का उपयोग करती है, एक गैर-गणनीय फ़ंक्शन की गणना कर सकती है।[21] मानक क्वबिट-मॉडल एक कंप्यूटर जितना का उपयोग करना संभव नहीं है, क्योंकि यह सिद्ध है कि एक नियमित क्वांटम कंप्यूटर पीएसपीएसीई-कमी|पीएसपीएसीई-रिड्यूसिबल है (बहुपद समय में चलने वाला क्वांटम कंप्यूटर बहुपद स्थान में चलने वाले शास्त्रीय कंप्यूटर द्वारा अनुकरण किया जा सकता है) .[22]
आख़िरकार सही सिस्टम
कुछ भौतिक रूप से साकार करने योग्य प्रणालियाँ हमेशा अंततः सही उत्तर पर आ जाती हैं, परंतु उनमें दोष यह है कि वे अक्सर गलत उत्तर देते हैं और अंततः वापस जाने और गलती को सुधारने से पहले असंगत रूप से बड़ी अवधि के लिए गलत उत्तर पर टिके रहते हैं।
- 1960 के दशक के मध्य में, ई मार्क गोल्ड और हिलेरी पटनम ने स्वतंत्र रूप से आगमनात्मक अनुमान (सीमित पुनरावर्ती कार्यात्मकता) के मॉडल प्रस्तावित किए[23] और परीक्षण-और-त्रुटि विधेय,[24] क्रमश)। ये मॉडल संख्याओं या भाषाओं के कुछ गैर-पुनरावर्ती सेट (भाषाओं के सभी पुनरावर्ती गणनीय सेट सहित) को सीमा में सीखने में सक्षम बनाते हैं; जबकि, परिभाषा के अनुसार, ट्यूरिंग मशीन द्वारा संख्याओं या भाषाओं के केवल पुनरावर्ती सेट की पहचान की जा सकती है। जबकि मशीन कुछ सीमित समय में किसी भी सीखने योग्य सेट पर सही उत्तर पर स्थिर हो जाएगी, यह केवल इसे सही के रूप में पहचान सकती है यदि यह पुनरावर्ती है; अन्यथा, शुद्धता केवल मशीन को हमेशा चलाने और यह ध्यान देने से ही स्थापित होती है कि यह अपने उत्तर को कभी संशोधित नहीं करती है। पुत्नाम ने इस नई व्याख्या को अनुभवजन्य विधेय के वर्ग के रूप में पहचाना, कहा: यदि हम हमेशा 'मानते' हैं कि सबसे हाल ही में उत्पन्न उत्तर सही है, तो हम सीमित संख्या में गलतियाँ करेंगे, परंतु अंततः हमें सही उत्तर मिलेगा। (ध्यान दें, हालांकि, भले ही हमें सही उत्तर (सीमित अनुक्रम का अंत) मिल गया हो, हम कभी भी आश्वस्त नहीं होते हैं कि हमारे पास सही उत्तर है।)[24]एल. के. शुबर्ट का 1974 का पेपर इटरेटेड लिमिटिंग रिकर्सन एंड द प्रोग्राम मिनिमाइजेशन प्रॉब्लम[25] सीमित प्रक्रिया को दोहराने के प्रभावों का अध्ययन किया; यह किसी भी अंकगणितीय पदानुक्रम विधेय की गणना करने की अनुमति देता है। शूबर्ट ने लिखा, सहज रूप से, पुनरावृत्त सीमित पहचान को निम्न क्रम आगमनात्मक अनुमान मशीनों के लगातार बढ़ते समुदाय द्वारा सामूहिक रूप से निष्पादित उच्च-क्रम आगमनात्मक अनुमान के रूप में माना जा सकता है।
- एक प्रतीक अनुक्रम सीमा में गणनीय है यदि सार्वभौमिक ट्यूरिंग मशीन पर एक सीमित, संभवतः गैर-रोकने वाला प्रोग्राम है जो अनुक्रम के प्रत्येक प्रतीक को क्रमिक रूप से आउटपुट करता है। इसमें π और प्रत्येक अन्य गणनीय वास्तविक का डायडिक विस्तार सम्मिलित है, परंतु फिर भी सभी गैर-गणनीय वास्तविकताओं को सम्मिलित नहीं किया गया है। पारंपरिक रूप से न्यूनतम विवरण लंबाई सिद्धांत में उपयोग की जाने वाली 'मोनोटोन ट्यूरिंग मशीनें' अपने पिछले आउटपुट को संपादित नहीं कर सकती हैं; सामान्यीकृत ट्यूरिंग मशीनें, जैसा कि जुर्गन श्मिडहुबर द्वारा परिभाषित किया गया है, कर सकती हैं। वह रचनात्मक रूप से वर्णन करने योग्य प्रतीक अनुक्रमों को उन लोगों के रूप में परिभाषित करता है जिनमें एक सामान्यीकृत ट्यूरिंग मशीन पर चलने वाला एक सीमित, गैर-रोक कार्यक्रम होता है, जैसे कि कोई भी आउटपुट प्रतीक अंततः परिवर्तित हो जाता है; अर्थात्, कुछ सीमित प्रारंभिक समय अंतराल के बाद इसमें कोई परिवर्तन नहीं होता है। कर्ट गोडेल (1931) द्वारा पहली बार प्रदर्शित सीमाओं के कारण, एक रुकावट कार्यक्रम द्वारा स्वयं अभिसरण समय की भविष्यवाणी करना असंभव हो सकता है, अन्यथा रुकने की समस्या हल हो सकती है। श्मिधुबर ([26][27]) औपचारिक रूप से वर्णित या रचनात्मक रूप से गणनीय ब्रह्मांडों या हर चीज के रचनात्मक सिद्धांत के सेट को परिभाषित करने के लिए इस दृष्टिकोण का उपयोग करता है। सामान्यीकृत ट्यूरिंग मशीनें अंततः स्पेकर अनुक्रम का मूल्यांकन करके रुकने की समस्या के सही समाधान में जुट सकती हैं।
क्षमताओं का विश्लेषण
कई हाइपरकंप्यूटेशन प्रस्तावों में ओरेकल मशीन या अन्यथा शास्त्रीय मशीन में एम्बेडेड सलाह (जटिलता) को पढ़ने के वैकल्पिक तरीके सम्मिलित हैं। अन्य लोग अंकगणितीय पदानुक्रम के कुछ उच्च स्तर तक पहुंच की अनुमति देते हैं। उदाहरण के लिए, सुपरटास्किंग ट्यूरिंग मशीनें, सामान्य धारणाओं के तहत, सत्य-तालिका कमी में किसी भी विधेय की गणना करने में सक्षम होंगी | सत्य-तालिका डिग्री युक्त या . इसके विपरीत, सीमित-पुनरावर्तन, संबंधित ट्यूरिंग डिग्री में किसी भी विधेय या फ़ंक्शन की गणना कर सकता है, जिसे जाना जाता है . गोल्ड ने आगे दिखाया कि आंशिक रिकर्सन को सीमित करने से सटीक गणना की अनुमति मिल जाएगी विधेय.
Model | Computable predicates | Notes | Refs |
---|---|---|---|
supertasking | tt() | dependent on outside observer | [28] |
limiting/trial-and-error | [23] | ||
iterated limiting (k times) | [25] | ||
Blum–Shub–Smale machine | incomparable with traditional computable real functions | [29] | |
Malament–Hogarth spacetime | HYP | dependent on spacetime structure | [30] |
analog recurrent neural network | f is an advice function giving connection weights; size is bounded by runtime | [31][32] | |
infinite time Turing machine | Arithmetical Quasi-Inductive sets | [33] | |
classical fuzzy Turing machine | for any computable t-norm | [8] | |
increasing function oracle | for the one-sequence model; are r.e. | [11] |
आलोचना
मार्टिन डेविस (गणितज्ञ) ने हाइपरकंप्यूटेशन पर अपने लेखन में,[34][35] इस विषय को एक मिथक के रूप में संदर्भित करता है और इसके प्रति-तर्क प्रस्तुत करता है हाइपरकंप्यूटेशन की भौतिक प्राप्ति। जहां तक इसके सिद्धांत का सवाल है, वह इसके ख़िलाफ़ तर्क देते हैं दावा है कि यह 1990 के दशक में स्थापित एक नया क्षेत्र है। यह दृष्टिकोण निर्भर करता है कम्प्यूटेबिलिटी सिद्धांत के इतिहास पर (असॉल्वेबिलिटी की डिग्री, कम्प्यूटेबिलिटी खत्म)। फ़ंक्शन, वास्तविक संख्याएं और क्रमसूचक), जैसा कि ऊपर भी बताया गया है। अपने तर्क में, उन्होंने एक टिप्पणी की कि सभी हाइपरकंप्यूटेशन इससे थोड़ा अधिक है: यदि गैर-गणनीय इनपुट की अनुमति है, तो गैर-गणनीय आउटपुट प्राप्य हैं।[36]
यह भी देखें
- गणना
- डिजिटल भौतिकी
- गणना की सीमाएँ
- सुपरटास्क
संदर्भ
- ↑ Turing, A. M. (1939). "Systems of Logic Based on Ordinals†". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
- ↑ "Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper Systems of Logic Based On Ordinals)
- ↑ J. Cabessa; H.T. Siegelmann (Apr 2012). "इंटरएक्टिव आवर्ती तंत्रिका नेटवर्क की कम्प्यूटेशनल शक्ति" (PDF). Neural Computation. 24 (4): 996–1019. CiteSeerX 10.1.1.411.7540. doi:10.1162/neco_a_00263. PMID 22295978. S2CID 5826757.
- ↑ Arnold Schönhage, "On the power of random access machines", in Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 520–529, 1979. Source of citation: Scott Aaronson, "NP-complete Problems and Physical Reality"[1] p. 12
- ↑ Andrew Hodges. "प्रोफेसर और मंथन". The Alan Turing Home Page. Retrieved 23 September 2011.
- ↑ H.T. Siegelmann; E.D. Sontag (1994). "तंत्रिका नेटवर्क के माध्यम से एनालॉग संगणना". Theoretical Computer Science. 131 (2): 331–360. doi:10.1016/0304-3975(94)90178-3.
- ↑ Biacino, L.; Gerla, G. (2002). "अस्पष्ट तर्क, निरंतरता और प्रभावशीलता". Archive for Mathematical Logic. 41 (7): 643–667. CiteSeerX 10.1.1.2.8029. doi:10.1007/s001530100128. ISSN 0933-5846. S2CID 12513452.
- ↑ 8.0 8.1 Wiedermann, Jiří (2004). "शास्त्रीय फ़ज़ी ट्यूरिंग मशीनों की सुपर-ट्यूरिंग कंप्यूटिंग शक्ति और दक्षता की विशेषता". Theoretical Computer Science. 317 (1–3): 61–69. doi:10.1016/j.tcs.2003.12.004.
उनकी (रुकने की समस्या को हल करने की क्षमता) उनकी स्वीकृति मानदंड के कारण होती है जिसमें रुकने की समस्या को हल करने की क्षमता परोक्ष रूप से मानी जाती है।
- ↑ Edith Spaan; Leen Torenvliet; Peter van Emde Boas (1989). "गैर-नियतिवाद, निष्पक्षता और एक मौलिक सादृश्य". EATCS Bulletin. 37: 186–193.
- ↑ Ord, Toby (2006). "हाइपरकंप्यूटेशन के कई रूप". Applied Mathematics and Computation. 178: 143–153. doi:10.1016/j.amc.2005.09.076.
- ↑ 11.0 11.1 Dmytro Taranovsky (July 17, 2005). "फ़िनिटिज़्म और हाइपरकंप्यूटेशन". Retrieved Apr 26, 2011.
- ↑ Hewitt, Carl. "What Is Commitment." Physical, Organizational, and Social (Revised), Coordination, Organizations, Institutions, and Norms in Agent Systems II: AAMAS (2006).
- ↑ These models have been independently developed by many different authors, including Hermann Weyl (1927). Philosophie der Mathematik und Naturwissenschaft.; the model is discussed in Shagrir, O. (June 2004). "Super-tasks, accelerating Turing machines and uncomputability". Theoretical Computer Science. 317 (1–3): 105–114. doi:10.1016/j.tcs.2003.12.007., Petrus H. Potgieter (July 2006). "Zeno machines and hypercomputation". Theoretical Computer Science. 358 (1): 23–33. arXiv:cs/0412022. doi:10.1016/j.tcs.2005.11.040. S2CID 6749770. and Vincent C. Müller (2011). "On the possibilities of hypercomputing supertasks". Minds and Machines. 21 (1): 83–96. CiteSeerX 10.1.1.225.3696. doi:10.1007/s11023-011-9222-6. S2CID 253434.
- ↑ Andréka, Hajnal; Németi, István; Székely, Gergely (2012). "सापेक्ष संगणना में बंद टाइमलाइक वक्र". Parallel Processing Letters. 22 (3). arXiv:1105.0047. doi:10.1142/S0129626412400105. S2CID 16816151.
- ↑ Hogarth, Mark L. (1992). "Does general relativity allow an observer to view an eternity in a finite time?". Foundations of Physics Letters. 5 (2): 173–181. Bibcode:1992FoPhL...5..173H. doi:10.1007/BF00682813. S2CID 120917288.
- ↑ István Neméti; Hajnal Andréka (2006). "Can General Relativistic Computers Break the Turing Barrier?". Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings. Lecture Notes in Computer Science. Vol. 3988. Springer. doi:10.1007/11780342. ISBN 978-3-540-35466-6.
- ↑ Etesi, Gabor; Nemeti, Istvan (2002). "मैलामेंट-हॉगर्थ स्पेस-टाइम के माध्यम से गैर-ट्यूरिंग गणना". International Journal of Theoretical Physics. 41 (2): 341–370. arXiv:gr-qc/0104023. doi:10.1023/A:1014019225365. S2CID 17081866.
- ↑ Earman, John; Norton, John D. (1993). "Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes". Philosophy of Science. 60: 22–42. doi:10.1086/289716. S2CID 122764068.
- ↑ Brun, Todd A. (2003). "बंद टाइमलाइक वक्र वाले कंप्यूटर कठिन समस्याओं को हल कर सकते हैं". Found. Phys. Lett. 16 (3): 245–253. arXiv:gr-qc/0209061. doi:10.1023/A:1025967225931. S2CID 16136314.
- ↑ S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [2]
- ↑ There have been some claims to this effect; see Tien Kieu (2003). "Quantum Algorithm for the Hilbert's Tenth Problem". Int. J. Theor. Phys. 42 (7): 1461–1478. arXiv:quant-ph/0110136. doi:10.1023/A:1025780028846. S2CID 6634980. or M. Ziegler (2005). "Computational Power of Infinite Quantum Parallelism". International Journal of Theoretical Physics. 44 (11): 2059–2071. arXiv:quant-ph/0410141. Bibcode:2005IJTP...44.2059Z. doi:10.1007/s10773-005-8984-0. S2CID 9879859. and the ensuing literature. For a retort see Warren D. Smith (2006). "Three counterexamples refuting Kieu's plan for "quantum adiabatic hypercomputation"; and some uncomputable quantum mechanical tasks". Applied Mathematics and Computation. 178 (1): 184–193. doi:10.1016/j.amc.2005.09.078..
- ↑ Bernstein, Ethan; Vazirani, Umesh (1997). "क्वांटम जटिलता सिद्धांत". SIAM Journal on Computing. 26 (5): 1411–1473. doi:10.1137/S0097539796300921.
- ↑ 23.0 23.1 E. M. Gold (1965). "सीमित प्रत्यावर्तन". Journal of Symbolic Logic. 30 (1): 28–48. doi:10.2307/2270580. JSTOR 2270580. S2CID 33811657., E. Mark Gold (1967). "Language identification in the limit". Information and Control. 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5.
- ↑ 24.0 24.1 Hilary Putnam (1965). "परीक्षण और त्रुटि भविष्यवाणी और मोस्टोवेक्सी की समस्या का समाधान". Journal of Symbolic Logic. 30 (1): 49–57. doi:10.2307/2270581. JSTOR 2270581. S2CID 44655062.
- ↑ 25.0 25.1 L. K. Schubert (July 1974). "पुनरावृत्त सीमित प्रत्यावर्तन और प्रोग्राम न्यूनीकरण समस्या". Journal of the ACM. 21 (3): 436–445. doi:10.1145/321832.321841. S2CID 2071951.
- ↑ Schmidhuber, Juergen (2000). "हर चीज़ के एल्गोरिथम सिद्धांत". arXiv:quant-ph/0011122.
- ↑ J. Schmidhuber (2002). "सामान्यीकृत कोलमोगोरोव जटिलताओं के पदानुक्रम और सीमा में गणना योग्य अनगिनत सार्वभौमिक उपाय". International Journal of Foundations of Computer Science. 13 (4): 587–612. arXiv:quant-ph/0011122. Bibcode:2000quant.ph.11122S. doi:10.1142/S0129054102001291.
- ↑ Petrus H. Potgieter (July 2006). "Zeno machines and hypercomputation". Theoretical Computer Science. 358 (1): 23–33. arXiv:cs/0412022. doi:10.1016/j.tcs.2005.11.040. S2CID 6749770.
- ↑ Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale (1998). Complexity and Real Computation. ISBN 978-0-387-98281-6.
{{cite book}}
: CS1 maint: multiple names: authors list (link) - ↑ P.D. Welch (2008). "The extent of computation in Malament-Hogarth spacetimes". British Journal for the Philosophy of Science. 59 (4): 659–674. arXiv:gr-qc/0609035. doi:10.1093/bjps/axn031.
- ↑ H.T. Siegelmann (Apr 1995). "Computation Beyond the Turing Limit" (PDF). Science. 268 (5210): 545–548. Bibcode:1995Sci...268..545S. doi:10.1126/science.268.5210.545. PMID 17756722. S2CID 17495161.
- ↑ Hava Siegelmann; Eduardo Sontag (1994). "Analog Computation via Neural Networks". Theoretical Computer Science. 131 (2): 331–360. doi:10.1016/0304-3975(94)90178-3.
- ↑ P.D. Welch (2009). "Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems". Theoretical Computer Science. 410 (4–5): 426–442. doi:10.1016/j.tcs.2008.09.050.
- ↑ Davis, Martin (2006). "हाइपरकंप्यूटेशन जैसा कोई अनुशासन क्यों नहीं है?". Applied Mathematics and Computation. 178 (1): 4–7. doi:10.1016/j.amc.2005.09.066.
- ↑ Davis, Martin (2004). "The Myth of Hypercomputation". Alan Turing: Life and Legacy of a Great Thinker. Springer.
- ↑ Martin Davis (Jan 2003). "The Myth of Hypercomputation". In Alexandra Shlapentokh (ed.). Miniworkshop: Hilbert's Tenth Problem, Mazur's Conjecture and Divisibility Sequences (PDF). MFO Report. Vol. 3. Mathematisches Forschungsinstitut Oberwolfach. p. 2.
अग्रिम पठन
- Mario Antoine Aoun, "Advances in Three Hypercomputation Models", (2016)
- L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
- Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289–1293
- Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
- Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
- Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
- Cooper, S. B. (2006). "Definability as hypercomputational effect" (PDF). Applied Mathematics and Computation. 178: 72–82. CiteSeerX 10.1.1.65.4088. doi:10.1016/j.amc.2005.09.072. S2CID 1487739. Archived from the original (PDF) on 2011-07-24. Retrieved 2011-06-16.
- Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature" (PDF). In S. B. Cooper; S. S. Goncharov (eds.). Computability and Models: Perspectives East and West. Plenum Publishers, New York, Boston, Dordrecht, London, Moscow. pp. 137–160. Archived from the original (PDF) on 2011-07-24. Retrieved 2011-06-16.
- Copeland, J. (2002) Hypercomputation Archived 2016-03-14 at the Wayback Machine, Minds and machines, v. 12, pp. 461–502
- Davis, Martin (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. The requested URL /~simon/TEACH/28000/DavisUniversal.pdf was not found on this server. Lecture Notes in Computer Science, 3988 pp. 125–132
- Hagar, A. and Korolev, A., Quantum Hypercomputation—Hype or Computation?, (2007)
- Müller, Vincent C. (2011). "On the possibilities of hypercomputing supertasks". Minds and Machines. 21 (1): 83–96. CiteSeerX 10.1.1.225.3696. doi:10.1007/s11023-011-9222-6. S2CID 253434.
- Ord, Toby. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
- Piccinini, Gualtiero: Computation in Physical Systems
- Putz, Volkmar and Karl Svozil, Can a computer be "pushed" to perform faster-than-light?, (2010)
- Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts
- Mike Stannett, Mike (1990). "X-machines and the halting problem: Building a super-Turing machine". Formal Aspects of Computing. 2 (1): 331–341. doi:10.1007/BF01888233. S2CID 7406983.
- Mike Stannett, The case for hypercomputation Archived 2016-03-04 at the Wayback Machine, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8–24, Special Issue on Hypercomputation
- Syropoulos, Apostolos (2008), Hypercomputation: Computing Beyond the Church–Turing Barrier (preview), Springer. ISBN 978-0-387-30886-9
- Turing, Alan (1939). "Systems of logic based on ordinals". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
- Ashish Sharma (2022), Nature Inspired Algorithms with Randomized Hypercomputational Perspective. Information Sciences. https://doi.org/10.1016/j.ins.2022.05.020