हाइपरकंप्यूटेशन

From Vigyanwiki
Revision as of 18:13, 20 July 2023 by alpha>Indicwiki (Created page with "{{short description|Models of computation that provide outputs that are not Turing-computable}} हाइपरकंप्यूटेशन या सुपर-ट्य...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

हाइपरकंप्यूटेशन या सुपर-ट्यूरिंग कंप्यूटेशन, कंप्यूटेशन के मॉडल का एक सेट है जो ऐसे आउटपुट प्रदान कर सकता है जो ट्यूरिंग-कम्प्यूटेबल योग्य नहीं हैं। सुपर-ट्यूरिंग कंप्यूटिंग, जिसे 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]


यह भी देखें

संदर्भ

  1. 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.
  2. "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)
  3. 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.
  4. 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
  5. Andrew Hodges. "प्रोफेसर और मंथन". The Alan Turing Home Page. Retrieved 23 September 2011.
  6. H.T. Siegelmann; E.D. Sontag (1994). "तंत्रिका नेटवर्क के माध्यम से एनालॉग संगणना". Theoretical Computer Science. 131 (2): 331–360. doi:10.1016/0304-3975(94)90178-3.
  7. 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. 8.0 8.1 Wiedermann, Jiří (2004). "शास्त्रीय फ़ज़ी ट्यूरिंग मशीनों की सुपर-ट्यूरिंग कंप्यूटिंग शक्ति और दक्षता की विशेषता". Theoretical Computer Science. 317 (1–3): 61–69. doi:10.1016/j.tcs.2003.12.004. उनकी (रुकने की समस्या को हल करने की क्षमता) उनकी स्वीकृति मानदंड के कारण होती है जिसमें रुकने की समस्या को हल करने की क्षमता परोक्ष रूप से मानी जाती है।
  9. Edith Spaan; Leen Torenvliet; Peter van Emde Boas (1989). "गैर-नियतिवाद, निष्पक्षता और एक मौलिक सादृश्य". EATCS Bulletin. 37: 186–193.
  10. Ord, Toby (2006). "हाइपरकंप्यूटेशन के कई रूप". Applied Mathematics and Computation. 178: 143–153. doi:10.1016/j.amc.2005.09.076.
  11. 11.0 11.1 Dmytro Taranovsky (July 17, 2005). "फ़िनिटिज़्म और हाइपरकंप्यूटेशन". Retrieved Apr 26, 2011.
  12. Hewitt, Carl. "What Is Commitment." Physical, Organizational, and Social (Revised), Coordination, Organizations, Institutions, and Norms in Agent Systems II: AAMAS (2006).
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. Brun, Todd A. (2003). "बंद टाइमलाइक वक्र वाले कंप्यूटर कठिन समस्याओं को हल कर सकते हैं". Found. Phys. Lett. 16 (3): 245–253. arXiv:gr-qc/0209061. doi:10.1023/A:1025967225931. S2CID 16136314.
  20. S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [2]
  21. 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..
  22. Bernstein, Ethan; Vazirani, Umesh (1997). "क्वांटम जटिलता सिद्धांत". SIAM Journal on Computing. 26 (5): 1411–1473. doi:10.1137/S0097539796300921.
  23. 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. 24.0 24.1 Hilary Putnam (1965). "परीक्षण और त्रुटि भविष्यवाणी और मोस्टोवेक्सी की समस्या का समाधान". Journal of Symbolic Logic. 30 (1): 49–57. doi:10.2307/2270581. JSTOR 2270581. S2CID 44655062.
  25. 25.0 25.1 L. K. Schubert (July 1974). "पुनरावृत्त सीमित प्रत्यावर्तन और प्रोग्राम न्यूनीकरण समस्या". Journal of the ACM. 21 (3): 436–445. doi:10.1145/321832.321841. S2CID 2071951.
  26. Schmidhuber, Juergen (2000). "हर चीज़ के एल्गोरिथम सिद्धांत". arXiv:quant-ph/0011122.
  27. 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.
  28. 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.
  29. 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)
  30. 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.
  31. 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.
  32. 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.
  33. 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.
  34. Davis, Martin (2006). "हाइपरकंप्यूटेशन जैसा कोई अनुशासन क्यों नहीं है?". Applied Mathematics and Computation. 178 (1): 4–7. doi:10.1016/j.amc.2005.09.066.
  35. Davis, Martin (2004). "The Myth of Hypercomputation". Alan Turing: Life and Legacy of a Great Thinker. Springer.
  36. 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.


अग्रिम पठन


बाहरी संबंध