रजिस्टर मशीन

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

अवलोकन

रजिस्टर मशीन को उसका नाम प्रोसेसर रजिस्टर के उपयोग से मिला हैं। ट्यूरिंग मशीन द्वारा उपयोग किए जाने वाले टेप और सिर के विपरीत, मॉडल एकाधिक, विशिष्ट रूप से संबोधित रजिस्टरों का उपयोग करता है, जिनमें से प्रत्येक में सकारात्मक पूर्णांक होता है।

साहित्य रूप से कम से कम चार उप-वर्ग बनाए गए हैं, जिसमे सबसे विशेष रूप से कंप्यूटर के उपयोग के माध्यम से सबसे अधिक सरलता से सूचीबद्ध हैं:

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

कोई भी ठीक से परिभाषित रजिस्टर मशीन मॉडल ट्यूरिंग पूर्णता होती है। कम्प्यूटरीकृत गति प्रारूप की विशेष रूप से बहुत निर्भर है।

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

औपचारिक परिभाषा

एक रजिस्टर मशीन में सम्मलित हैं:

1. लेबल किए गए, असतत, असीमित रजिस्टरों की असीमित संख्या सीमा (क्षमता) में असीमित: रजिस्टरों का परिमित (या कुछ मॉडलों में अनंत) सेट $r_{0}\ldots r_{n}$ प्रत्येक को अनंत सीमा का माना जाता है और जिनमें से प्रत्येक में गैर-ऋणात्मक पूर्णांक (0, 1, 2, ...) होता है। रजिस्टर अपना अंकगणित कर सकते हैं, या इससे अधिक विशेष रजिस्टर हो सकते हैं जो अंकगणित करते हैं। उदाहरण के लिए संचायक और/या पता रजिस्टर तथा रैंडम-एक्सेस मशीन इसका मुख्य उदाहरण हैं।
2. 'टैली काउंटर या निशान': असतत, अप्रभेद्य वस्तुएं या मॉडल के लिए उपयुक्त केवल प्रकार के निशान उपलब्ध रहते हैं। सबसे कम काउंटर मशीन मॉडल में, प्रत्येक अंकगणितीय ऑपरेशन के अनुसार केवल वस्तु/चिह्न को उसके स्थान/टेप से जोड़ा या हटाया जाता है। कुछ काउंटर मशीन मॉडल में (जैसे मेल्ज़ाक (1961), मिन्स्की (1961)) और अधिकांश रैम और आरएएसपी मॉडल में से अधिक ऑब्जेक्ट/मार्क को ऑपरेशन में जोड़ा या हटाया जा सकता है और सामान्यतः घटाव के लिए तथा कभी-कभी गुणा और/या भाग के साथ उपयोग किया जाता हैं। कुछ मॉडलों में नियंत्रण संचालन होते हैं जैसे कॉपी (विभिन्न: मूव, लोड, स्टोर) जो क्रिया में रजिस्टर से रजिस्टर करने के लिए ऑब्जेक्ट्स/मार्क्स के क्लंप को स्थानांतरित करते हैं।
3. A (बहुत) निर्देशों का सीमित सेट: निर्देश दो वर्गों अंकगणित और नियंत्रण में विभाजित होते हैं। निर्देश-सेट बनाने के लिए निर्देश दो वर्गों से तैयार किए जाते हैं, जैसे कि निर्देश सेट को मॉडल को ट्यूरिंग समतुल्य होने की अनुमति देनी चाहिए (यह किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना करने में सक्षम होना चाहिए)।
   1. अंकगणित: अंकगणितीय निर्देश सभी रजिस्टरों पर या सिर्फ विशेष रजिस्टर (जैसे संचायक) पर कार्य कर सकते हैं। वे सामान्यतः निम्नलिखित सेटों में से चुने जाते हैं (किन्तु अपवाद सामान्य हैं):
      • काउंटर मशीन: { इंक्रीमेंट (आर), डिक्रीमेंट (आर), क्लियर-टू-जीरो (आर)}
      • कम रैम, रैस्प: { इंक्रीमेंट (r), डिक्रीमेंट (r), क्लियर-टू-जीरो (r), लोड-तत्काल-स्थिर k, जोड़ें (r)₁,आर₂), उचित-घटाना (आर₁,आर₂), इंक्रीमेंट एक्युमुलेटर, डिक्रीमेंट एक्युमुलेटर, क्लीयर एक्युमुलेटर, रजिस्टर आर के एक्युमुलेटर कंटेंट में जोड़ें, रजिस्टर आर के एक्युमुलेटर कंटेंट से प्रॉपर-घटाना, }
      • संवर्धित रैम, रैस्प: सभी कम किए गए निर्देश प्लस: {गुणा करें, विभाजित करें, विभिन्न बूलियन बिट-वाइज़ (लेफ्ट-शिफ्ट, बिट टेस्ट, आदि)}
   2. नियंत्रण:
      • काउंटर मशीन मॉडल: वैकल्पिक {कॉपी (R₁,R₂)}
      • रैम और रैस्प मॉडल: अधिकांश में {प्रतिलिपि (R₁,R₂) }, या {आर से लोड संचायक, आर में स्टोर संचायक, तत्काल स्थिरांक के साथ लोड संचयकर्ता}
      • सभी मॉडल: रजिस्टर के परीक्षण के बाद कम से कम सशर्त छलांग (शाखा, गोटो)। { जंप-इफ-जीरो, जंप-इफ-नॉट-जीरो (अर्ताथ जंप-इफ-पॉजिटिव), जंप-इफ-इक्वल, जंप-इफ-नॉट इक्वल}
      • सभी मॉडल वैकल्पिक: {बिना शर्त प्रोग्राम जंप (गोटो)}
   3. 'रजिस्टर-एड्रेसिंग विधि':
      • काउंटर मशीन: कोई अप्रत्यक्ष संबोधन नहीं, अत्यधिक एटमाइज्ड मॉडल में तत्काल ऑपरेंड संभव है
      • रैम और रैस्प: इनडायरेक्ट एड्रेसिंग उपलब्ध, तत्काल ऑपरेंड विशिष्ट
   4. 'इनपुट-आउटपुट': सभी मॉडलों में वैकल्पिक
4. 'स्थिति रजिस्टर': विशेष निर्देश रजिस्टर आईआर, परिमित और उपरोक्त रजिस्टरों से अलग, वर्तमान निर्देश को निष्पादित करने के लिए संग्रहीत करता है और इसका पता निर्देशों की तालिका में होता है; यह रजिस्टर और इसकी तालिका परिमित अवस्था मशीन में स्थित है।
   • आईआर सभी मॉडलों के लिए ऑफ-लिमिट है। रैम और आरएएसपी की स्थिति में, रजिस्टर के पते का निर्धारण करने के प्रयोजनों के लिए, मॉडल या तो (i) सीधे संबोधित करने की स्थिति में - तालिका द्वारा निर्दिष्ट पता और आईआर में अस्थायी रूप से स्थित या (ii) का चयन कर सकता है। अप्रत्यक्ष पते की स्थिति में - आईआर के निर्देश द्वारा निर्दिष्ट रजिस्टर की सामग्री उपलब्ध हैं।
   • आईआर रैस्प (या पारंपरिक कंप्यूटर) का प्रोग्राम काउंटर (PC) नहीं है। पीसी संचायक के समान और रजिस्टर है, किन्तु आरएएसपी के वर्तमान रजिस्टर-आधारित निर्देश की संख्या को धारण करने के लिए समर्पित है। इस प्रकार रैस्प के पास दो निर्देश/कार्यक्रम रजिस्टर होते हैं- (i) IR (परिमित स्थिति मशीन का निर्देश रजिस्टर), और (ii) रजिस्टरों में स्थित कार्यक्रम के लिए पीसी (प्रोग्राम काउंटर)। (साथ ही साथ पीसी को समर्पित रजिस्टर, आरएएसपी प्रोग्राम-इंस्ट्रक्शन रजिस्टर (पीआईआर, आईआर, पीआर, आदि जैसे किसी भी नाम से जाने वाले) के लिए और रजिस्टर समर्पित कर सकता है।
5. 'लेबल निर्देशों की सूची, सामान्यतः अनुक्रमिक क्रम में': निर्देशों की सीमित सूची $I_{1}\ldots I_{m}$. काउंटर मशीन, रैंडम-एक्सेस मशीन (रैम) और पॉइंटर मशीन की स्थिति में निर्देश स्टोर परिमित स्थिति मशीन की तालिका में है; इस प्रकार ये मॉडल हार्वर्ड संरचना के उदाहरण हैं। आरएएसपी की स्थिति में प्रोग्राम स्टोर रजिस्टरों में है; इस प्रकार यह वॉन न्यूमैन संरचना का उदाहरण है। रैंडम-एक्सेस मशीन और रैंडम-एक्सेस स्टोर-प्रोग्राम मशीन भी देखें।
   सामान्यतः, कंप्यूटर प्रोग्राम की तरह, निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कूदना सफल नहीं होता तब तक डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इसका अपवाद एबैकस (लैम्बेक (1961), मिन्स्की (1961)) काउंटर मशीन मॉडल है- प्रत्येक निर्देश में कम से कम अगला निर्देश पहचानकर्ता z होता है, और सशर्त शाखा में दो होते हैं।
   • ध्यान दें कि अबेकस मॉडल दो निर्देशों को जोड़ता है, JZ फिर DEC: उदा. { कांग्रेस (आर, जेड), जेडडीईसी (आर, जेड_true, साथ_false ) }.
     सशर्त व्यंजक IF r=0 THEN z के बारे में अधिक जानकारी के लिए मैककार्थी औपचारिकता देखें_true अन्य जेड_false(सीएफ मैककार्थी (1960))।

रजिस्टर मशीन मॉडल का ऐतिहासिक विकास

1950 के दशक की प्रारंभ में दो रुझान दिखाई दिए- पहला कंप्यूटर को ट्यूरिंग मशीन के रूप में चिह्नित करने के लिए, दूसरा कंप्यूटर जैसे मॉडल को परिभाषित करने के लिए-अनुक्रमिक निर्देश अनुक्रम और सशर्त कूद वाले मॉडल-एक ट्यूरिंग मशीन की शक्ति के साथ, अर्ताथ तथाकथित ट्यूरिंग तुल्यता। इस कार्य की आवश्यकता दो कठिन समस्याओं के संदर्भ में की गई थी: एमिल पोस्ट द्वारा प्रस्तुत अघुलनशील शब्द समस्या- टैग की उनकी समस्या- और हिल्बर्ट की समस्याओं की बहुत कठिन समस्या- डायोफैंटाइन समीकरण के आसपास 10वां प्रश्न हैं। शोधकर्ता ट्यूरिंग-समतुल्य मॉडल की खोज कर रहे थे जो प्रकृति में कम तार्किक और अधिक अंकगणितीय थे (cf Melzak (1961) पृष्ठ 281, शेफर्डसन-स्टर्गिस (1963) पृष्ठ 218)।

पहली प्रवृत्ति-कंप्यूटर के लक्षण वर्णन की ओर-लगती है हैंस हेमीज़ (1954), रोज़ा पेटर (1958), और हेंज कफेंग्स्ट (1959) के साथ, हाओ वांग (अकादमिक) (1954, 1957) के साथ दूसरी प्रवृत्ति और, जैसा कि ऊपर उल्लेख किया गया है, Zdzislaw अलेक्जेंडर मेल्ज़ाक (1961) द्वारा आगे बढ़ाया गया, जोआचिम लैम्बेक (1961) और मार्विन मिंस्की (1961, 1967)।

पिछले पांच नामों को स्पष्ट रूप से यूरी मटियासेविच द्वारा उसी क्रम में सूचीबद्ध किया गया है। वह इसके साथ चलता है:

रजिस्टर मशीनें [कुछ लेखक काउंटर-मशीन के पर्यायवाची रजिस्टर मशीन का उपयोग करते हैं] डायोफैंटाइन समीकरणों के निर्माण के लिए विशेष रूप से उपयुक्त हैं। ट्यूरिंग मशीनों की तरह, उनके पास बहुत ही विशेष निर्देश हैं और, इसके अलावा, वे संख्याओं से निपटते हैं (यूरी मटियासेविच (1993), हिल्बर्ट की दसवीं समस्या, पुस्तक के अध्याय 5 की टिप्पणी, http://logic.pdmi.ras.ru/ पर युमैट/H10Pbook/commch_5htm. )

ऐसा प्रतीत होता है कि लैम्बेक, मेल्ज़ाक, मिंस्की और शेफर्डसन और स्टर्गिस ने स्वतंत्र रूप से ही समय में ही विचार का अनुमान लगाया था। वरीयता पर टिप्पणी नीचे देखें।

इतिहास की प्रारंभ वांग के मॉडल से होती है।

वांग का (1954, 1957) मॉडल: पोस्ट-ट्यूरिंग मशीन

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

{बाएं, दाएं, प्रिंट, JUMP_if_marked_to_instruction_z}

इन चारों को दोनों वांग (1954, 1957) और फिर सी. वाई. ली (1961) ने पोस्ट सेट {ERASE} से और निर्देश जोड़ा, और फिर पोस्ट की बिना शर्त छलांग {JUMP_to_instruction_z} (या चीजों को सरल बनाने के लिए, सशर्त कूद JUMP_IF_blank_to_instruction_z, या दोनों। ली ने इसे डब्ल्यू-मशीन मॉडल का नाम दिया:

{ बाएँ, दाएँ, प्रिंट करें, मिटाएँ, JUMP_if_marked, [शायद JUMP या JUMP_IF_blank] }

वांग ने आशा व्यक्त की कि उनका मॉडल ट्यूरिंग मशीनों के सिद्धांत और कंप्यूटर की व्यावहारिक दुनिया के बीच तालमेल (पृ. 63) होगा।

वांग का कार्य अत्यधिक प्रभावशाली था। हम उसे मिंस्की (1961) और (1967), मेल्ज़ाक (1961), शेफर्डसन और स्टर्गिस (1963) द्वारा संदर्भित पाते हैं। वास्तव में, शेफर्डसन और स्टर्गिस (1963) टिप्पणी करते हैं कि:

... हमने वैंग द्वारा सुझाई गई संगणना के व्यावहारिक और सैद्धांतिक पहलुओं के बीच कदम और आगे बढ़ने की कोशिश की है (पृ. 218)।

मार्टिन डेविस (गणितज्ञ) ने अंततः इस मॉडल को (2-प्रतीक) पोस्ट-ट्यूरिंग मशीन में विकसित किया।

वैंग/पोस्ट-ट्यूरिंग मॉडल के साथ कठिनाइयाँ:

सिवाय इसके कि कोई समस्या थी: वांग मॉडल (7-निर्देश पोस्ट-ट्यूरिंग मशीन के छह निर्देश) अभी भी एकल-टेप ट्यूरिंग-जैसी डिवाइस थी, चूंकि इसका क्रमिक कार्यक्रम निर्देश-प्रवाह अच्छा हो सकता है। मेलज़क (1961) और शेफर्डसन और स्टर्गिस (1963) दोनों ने इसे देखा (कुछ सबूतों और जांच के संदर्भ में):

... ट्यूरिंग मशीन में निश्चित अपारदर्शिता होती है... ट्यूरिंग मशीन (काल्पनिक) संचालन में धीमी होती है और सामान्यतः जटिल होती है। इससे इसे डिजाइन करना कठिन हो जाता है, और समय या भंडारण अनुकूलन या दो एल्गोरिदम की दक्षता के बीच तुलना जैसे मामलों की जांच करना भी कठिन हो जाता है। (मेल्ज़ाक (1961) पृष्ठ 281)

... चूंकि मुश्किल नहीं है ... प्रमाण दो कारणों से जटिल और थकाऊ हैं: (1) ट्यूरिंग मशीन में केवल सिर होता है जिससे कि अंक पर संचालन के बहुत छोटे चरणों में गणना को तोड़ने के लिए बाध्य हो . (2) इसमें केवल टेप होता है जिससे किसी को उस नंबर को खोजने के लिए कुछ परेशानी में पड़ना पड़ता है जिस पर वह कार्य करना चाहता है और उसे अन्य नंबरों से अलग रखता है (शेफर्डसन और स्टर्गिस (1963) पृष्ठ 218)।

दरअसल, ट्यूरिंग मशीन के उदाहरण, पोस्ट-ट्यूरिंग मशीन और आंशिक फ़ंक्शन शो के उदाहरण के रूप में, कार्य जटिल हो सकता है।

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

हमें केवल अपने निर्देशों को लिखने में सावधानी बरतनी है जिससे कि शून्य के लिए परीक्षण हो और घटने से पहले कूद जाए अन्यथा हमारी मशीन अंत से गिर जाएगी या अंत से टकरा जाएगी - हमारे पास आंशिक कार्य का उदाहरण होगा। घटने से पहले हमारी मशीन को हमेशा यह सवाल पूछना चाहिए: क्या टेप/काउंटर खाली है? यदि ऐसा है तो मैं घट नहीं सकता, अन्यथा मैं कर सकता हूँ।

मिन्स्की (1961) और शेफर्डसन-स्टर्गिस (1963) साबित करते हैं कि केवल कुछ टेप- जितने कम एक-अभी भी मशीन को ट्यूरिंग समतुल्य होने की अनुमति देते हैं यदि टेप पर डेटा को गोडेल नंबर (या कुछ अन्य विशिष्ट रूप से एनकोडेबल-) के रूप में दर्शाया जाता है। डिकोडेबल नंबर); गणना आगे बढ़ने पर यह संख्या विकसित होगी। गोडेल संख्या एन्कोडिंग वाले टेप संस्करण में काउंटर मशीन को (i) गोडेल संख्या को स्थिरांक (संख्या 2 या 3) से गुणा करने में सक्षम होना चाहिए, और (ii) स्थिरांक (संख्या 2 या 3) से विभाजित करना चाहिए और कूदना चाहिए यदि शेष शून्य है। मिंस्की (1967) ने दिखाया कि इस विचित्र निर्देश सेट की आवश्यकता को {INC (r), JZDEC (r, z)} और सुविधा निर्देश {CLR (r), J (r)} में शिथिल किया जा सकता है यदि दो टेप उपलब्ध हैं . चूंकि, साधारण गोडेलाइज़ेशन अभी भी आवश्यक है। उनके आरएएसपी मॉडल के संबंध में एल्गोट-रॉबिन्सन (1964) में समान परिणाम दिखाई देता है।

मेल्ज़ाक (1961) का मॉडल अलग है: कंकड़ के गुच्छे छिद्रों में और बाहर जाते हैं

Melzak's (1961) मॉडल काफी अलग है। उन्होंने अपना खुद का मॉडल लिया, टेपों को लंबवत रूप से फ़्लिप किया, उन्हें कंकड़ काउंटरों से भरने के लिए जमीन में छेद कहा। मिन्स्की की वृद्धि और गिरावट के विपरीत, मेल्ज़ाक ने कंकड़ की किसी भी गिनती के उचित घटाव की अनुमति दी और कंकड़ की किसी भी गिनती को जोड़ दिया।

वह अपने मॉडल (पृष्ठ 288) के लिए अप्रत्यक्ष संबोधन को परिभाषित करता है और इसके उपयोग के दो उदाहरण प्रदान करता है (पृष्ठ 89); उसका प्रमाण (पृ. 290-292) कि उसका मॉडल ट्यूरिंग समतुल्य है, इतना अस्पष्ट है कि पाठक यह नहीं बता सकता है कि वह अप्रत्यक्ष संबोधन को प्रमाण के लिए आवश्यकता होने की आशा रखता है या नहीं।

मेलज़क के मॉडल की मुख्य लैम्बेक का सरलीकरण और कुक एंड रेक्हो 1973 में उनके स्मरक सम्मेलनों का पुन: प्रकट होना है।

लैम्बेक (1961) ने मेल्ज़ाक के मॉडल को मिन्स्की (1961) मॉडल में परमाणुकृत किया: INC और DEC-with-test

लैम्बेक (1961) ने मेल्ज़ाक के त्रिगुट मॉडल को लिया और इसे दो एकात्मक निर्देशों-X+, X- यदि संभव हो तो कूदो-बिल्कुल वही दो जो मिन्स्की (1961) के साथ आए थे, के लिए परमाणुकृत किया।

चूंकि, मिन्स्की (1961) मॉडल की तरह, लैम्बेक मॉडल अपने निर्देशों को डिफ़ॉल्ट-अनुक्रमिक तरीके से निष्पादित करता है - X+ और X- दोनों अगले निर्देश के पहचानकर्ता को ले जाते हैं, और X- भी शून्य होने पर निर्देश पर कूदता है। -परीक्षण सफल रहा है।

एलगॉट-रॉबिन्सन (1964) और अप्रत्यक्ष समाधान के बिना रैस्प की समस्या

एक रैस्प या रैंडम-एक्सेस स्टोर्ड-प्रोग्राम मशीन काउंटर मशीन के रूप में प्रारंभ होती है, जिसके निर्देश के प्रोग्राम को इसके रजिस्टर में रखा जाता है। परिमित स्थिति मशीन के निर्देश रजिस्टर के अनुरूप, किन्तु स्वतंत्र, कम से कम रजिस्टर (प्रोग्राम काउंटर (पीसी) का उपनाम) और या से अधिक अस्थायी रजिस्टर वर्तमान निर्देश की संख्या का रिकॉर्ड बनाए रखते हैं और उस पर कार्य करते हैं। परिमित स्थिति मशीन के निर्देशों की तालिका (i) वर्तमान प्रोग्राम निर्देश को उचित रजिस्टर से लाने के लिए जिम्मेदार है, (ii) प्रोग्राम निर्देश को पार्स करना, (iii) प्रोग्राम निर्देश द्वारा निर्दिष्ट ऑपरेंड को लाना, और (iv) प्रोग्राम निर्देश को निष्पादित करना .

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

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

'कम्प्यूटेड गोटो:' निर्देशों का आरएएसपी प्रोग्राम जो सशर्त- या बिना शर्त-कूद कार्यक्रम निर्देश में गोटो पते को संशोधित करता है।

किन्तु यह समस्या का समाधान नहीं करता है (जब तक कि कोई गोडेल संख्या का सहारा नहीं लेता)। क्या आवश्यक है कार्यक्रम निर्देश का पता लाने के लिए विधि है जो परिमित स्थिति मशीन के निर्देश रजिस्टर और तालिका के ऊपरी सीमा से परे / ऊपर स्थित है।

उदाहरण: केवल चार असीमित रजिस्टरों से लैस काउंटर मशीन उदा। किसी भी दो संख्याओं (m, n) को साथ गुणा करके p— प्राप्त करें और इस प्रकार विशेष पुनरावर्ती फलन बनें—इससे कोई फर्क नहीं पड़ता कि संख्याएँ m और n कितनी बड़ी हैं; इसके अलावा, ऐसा करने के लिए 20 से कम निर्देशों की आवश्यकता होती है! उदा. { 1: CLR (p), 2: JZ (m, डन), 3 आउटर_लूप: JZ (n, डन), 4: CPY (m, temp), 5: इनर_लूप: JZ (m, आउटर_लूप), 6: DEC (एम), 7: आईएनसी (पी), 8: जे (इनर_लूप), 9: आउटर_लूप: डीईसी (एन), 10 जे (आउटर_लूप), एचएएलटी}

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

मिन्स्की (1967) निर्देशों {सीएलआर (आर), आईएनसी (आर), और आरपीटी (एक बार निर्देश एम से एन)} से लैस काउंटर मशीन (वह उन्हें प्रोग्राम कंप्यूटर मॉडल कहते हैं) की अपनी जांच में इस विवाद पर संकेत देता है। . वह हमें यह नहीं बताता कि समस्या को कैसे ठीक किया जाए, किन्तु वह देखता है कि:

... प्रोग्राम कंप्यूटर के पास यह ट्रैक रखने के लिए कोई तरीका होना चाहिए कि कितने RPT किए जाने बाकी हैं, और यह कंप्यूटर के परिमित भाग में अनुमत स्टोरेज की किसी विशेष मात्रा को समाप्त कर सकता है। सामान्य तौर पर, RPT संचालन के लिए अपने स्वयं के अनंत रजिस्टरों की आवश्यकता होती है, और हमारे द्वारा विचार किए गए अन्य प्रकार के संचालनों से अलग व्यवहार किया जाना चाहिए। (पृष्ठ 214)

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

उदाहरण: आईएनसी (आर_base, अनुक्रमणिका ) ; प्रभावी पता होगा [आर_base] + सूचकांक, जहां प्राकृतिक संख्या सूचकांक परिमित-स्थिति मशीन निर्देश से ही प्राप्त होता है।

हार्टमैनिस (1971)

1971 तक हार्टमैनिस ने अपने रैस्प मॉडल में उपयोग के लिए अनुक्रमण को अप्रत्यक्ष रूप से सरल बना दिया है।

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

ध्यान दें कि परिमित स्थिति मशीन को इस लक्ष्य रजिस्टर के पते को स्पष्ट रूप से निर्दिष्ट करने की आवश्यकता नहीं है। यह सिर्फ मशीन के बाकी हिस्सों से कहता है: मुझे मेरे पॉइंटर-रजिस्टर द्वारा बताए गए रजिस्टर की सामग्री प्राप्त करें और फिर इसके साथ xyz करें। इसे अपने निर्देश के माध्यम से स्पष्ट रूप से नाम से निर्दिष्ट करना होगा, यह पॉइंटर-रजिस्टर (जैसे N , या 72 या PC , आदि) किन्तु यह जानने की आवश्यकता नहीं है कि पॉइंटर-रजिस्टर में वास्तव में कौन सी संख्या है (शायद 279,431)।

=== कुक एंड रेक्हो (1973) रैम === का वर्णन करते हैं कुक एंड रेक्हो (1973) हार्टमैनिस (1971) का आशय देते हैं और अपने मॉडल को रैंडम-एक्सेस मशीन (रैम- अर्ताथ अप्रत्यक्ष और हार्वर्ड संरचना वाली मशीन) कहते हैं। मायने में हम मेल्ज़ाक (1961) में वापस आ गए हैं, किन्तु मेल्ज़क की तुलना में बहुत सरल मॉडल के साथ।

प्राथमिकता

मिन्स्की एमआईटी लिंकन प्रयोगशाला में कार्य कर रहे थे और उन्होंने वहां अपना कार्य प्रकाशित किया; उनका पेपर 15 अगस्त, 1960 को एनाल्स ऑफ मैथमेटिक्स में प्रकाशित होने के लिए प्राप्त हुआ था, किन्तु नवंबर 1961 तक प्रकाशित नहीं हुआ था। मेल्ज़ाक और लैम्बेक के कार्य के प्राप्त होने और प्रकाशित होने से पूरे साल पहले प्राप्ति हुई थी (क्रमशः मई और जून 15 प्राप्त हुआ था)। , 1961, और साथ-साथ सितंबर 1961 में प्रकाशित)। कि (i) दोनों कैनेडियन थे और कनाडाई गणितीय बुलेटिन में प्रकाशित हुए थे, (ii) दोनों में से किसी में भी मिंस्की के कार्य का संदर्भ नहीं होता क्योंकि यह अभी तक पीयर-रिव्यू जर्नल में प्रकाशित नहीं हुआ था, किन्तु (iii) मेल्ज़ाक वांग का संदर्भ देता है, और लैम्बेक संदर्भ मेलज़क, परिकल्पना की ओर ले जाता है कि उनका कार्य साथ और स्वतंत्र रूप से हुआ।

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

शेफर्डसन और स्टर्गिस का अंतिम पेपर 1963 तक सहकर्मी-समीक्षा पत्रिका में नहीं दिखाई दिया। और जैसा कि वे अपने परिशिष्ट ए में निष्पक्ष और ईमानदारी से नोट करते हैं, काफेंगस्ट (1959), एर्शोव (1958), पीटर (1958) के 'सिस्टम' सभी इतने समान हैं कि बाद में जो परिणाम प्राप्त हुए वे निम्नलिखित के सेट के लिए अप्रभेद्य हैं:

उत्पादन 0 अर्ताथ 0 → एन

एक संख्या बढ़ाएँ अर्थात n+1 → n

अर्थात उन संक्रियाओं को करने से जो प्राकृतिक संख्याएँ उत्पन्न करती हैं (पृ. 246)

एक नंबर अर्ताथ n → m कॉपी करें

एक गणना के पाठ्यक्रम को बदलने के लिए, या तो दो संख्याओं की तुलना करना या 0 तक घटाना

दरअसल, शेफर्सन और स्टर्गिस का निष्कर्ष है

विभिन्न न्यूनतम प्रणालियाँ बहुत समान हैं (पृष्ठ 246)

प्रकाशन तिथि के क्रम में काफेंगस्ट (1959), एर्शोव (1958), पीटर (1958) के कार्य पहले थे।

यह भी देखें

• काउंटर मशीन
  • काउंटर-मशीन मॉडल
• सूचक मशीन
• रैंडम-एक्सेस मशीन
• रैंडम-एक्सेस संग्रहीत प्रोग्राम मशीन
• ट्यूरिंग मशीन
  • यूनिवर्सल ट्यूरिंग मशीन
  • ट्यूरिंग मशीन गैलरी
  • ट्यूरिंग मशीन के उदाहरण
• वांग बी-मशीन
• पोस्ट-ट्यूरिंग मशीन - विवरण और उदाहरण
• कलन विधि
  • एल्गोरिथम लक्षण वर्णन
• रुकने की समस्या
• व्यस्त ऊदबिलाव
• स्टैक मशीन
• WDR पेपर कंप्यूटर

ग्रन्थसूची

Background texts: The following bibliography of source papers includes a number of texts to be used as background. The mathematics that led to the flurry of papers about abstract machines in the 1950s and 1960s can be found in van Heijenoort (1967)—an assemblage of original papers spanning the 50 years from Frege (1879) to Gödel (1931). Davis (ed.) The Undecidable (1965) carries the torch onward beginning with Gödel (1931) through Gödel's (1964) postscriptum (p. 71); the original papers of Alan Turing (1936-7) and Emil Post (1936) are included in The Undecidable. The mathematics of Church, Rosser and Kleene that appear as reprints of original papers in The Undecidable is carried further in Kleene (1952), a mandatory text for anyone pursuing a deeper understanding of the mathematics behind the machines. Both Kleene (1952) and Davis (1958) are referenced by a number of the papers.

For a good treatment of the counter machine see Minsky (1967) Chapter 11 "Models similar to Digital Computers"—he calls the counter machine a "progरैम computer". A recent overview is found at van Emde Boas (1990). A recent treatment of the Minsky (1961)/Lambek (1961) model can be found Boolos-Burgess-Jeffrey (2002); they reincarnate Lambek's "abacus model" to demonstrate equivalence of Turing machines and partial recursive functions, and they provide a graduate-level introduction to both abstract machine models (counter- and Turing-) and the mathematics of recursion theory. Beginning with the first edition Boolos-Burgess (1970) this model appeared with virtually the same treatment.

The papers: The papers begin with Wang (1957) and his dरैमatic simplification of the Turing machine. Turing (1936), Kleene (1952), Davis (1958) and in particular Post (1936) are cited in Wang (1957); in turn, Wang is referenced by Melzak (1961), Minsky (1961) and Shepherdson–Sturgis (1961-3) as they independently reduce the Turing tapes to "counters". Melzak (1961) provides his pebble-in-holes counter machine model with indirection but doesn't carry the treatment further. The work of Elgot–Robinson (1964) define the रैस्प—the computer-like random-access stored-progरैम machines—and appear to be the first to investigate the failure of the bounded counter machine to calculate the mu-recursive functions. This failure—except with the draconian use of Gödel numbers in the manner of Minsky (1961))—leads to their definition of "indexed" instructions (i.e. indirect addressing) for theआईआर रैस्प model. Elgot–Robinson (1964) and more so Hartmanis (1971) investigate रैस्पs with self-modifying progरैमs. Hartmanis (1971) specifies an instruction set with indirection, citing lecture notes of Cook (1970). For use in investigations of computational complexity Cook and his graduate student Reckhow (1973) provide the definition of a रैम (their model and mnemonic convention are similar to Melzak's, but offer him no reference in the paper). The pointer machines are an offshoot of Knuth (1968, 1973) and independently Schönhage (1980).

For the most part the papers contain mathematics beyond the undergraduate level—in particular the primitive recursive functions and mu recursive functions presented elegantly in Kleene (1952) and less in depth, but useful nonetheless, in Boolos-Burgess-Jeffrey (2002).

All texts and papers excepting the four starred have been witnessed. These four are written in German and appear as references in Shepherdson–Sturgis (1963) and Elgot–Robinson (1964); Shepherdson–Sturgis (1963) offer a brief discussion of their results in Shepherdson–Sturgis' Appendix A. The terminology of at least one paper (Kaphengst (1959) seems to hark back to the Burke-Goldstine-von Neumann (1946-7) analysis of computer architecture.

Author	Year	Reference	Turing machine	Counter machine	रैम	रैस्प	Pointer machine	Indirect addressing	Self-modifying progरैम
Goldstine & von Neumann	1947
Kleene	1952
*Hermes	1954, 5			?
Wang	1957			hints				hints
*Peter	1958			?
Davis	1958
*Ershov	1959			?
*Kaphengst	1959			?
Melzak	1961								hints
Lambek	1961
Minsky	1961
Shepherdson & Sturgis	1963							hints
Elgot & Robinson	1964
Davis- Undecidable	1965
van Heijenoort	1967
Minsky	1967				hints			hints
Knuth	1968, 73
Hartmanis	1971
Cook & Reckhow	1973
Schonhage	1980
van Emde Boas	1990
Boolos & Burgess; Boolos, Burgess & Jeffrey	1970–2002

संदर्भ

Notes

Sources

• George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
• Arthur Burks, Herman Goldstine, John von Neumann (1946), "Preliminary discussion of the logical design of an electronic computing instrument", reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4 .
• Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354–375.
• Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot and Abraham Robinson (1964), "Random-Access Stored-Program Machines, an Approach to Programming Languages", Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
• J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
• John Hopcroft, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
• Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
• Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
• Lambek, Joachim (September 1961). "How to Program an Infinite Abacus". Canadian Mathematical Bulletin. 4 (3): 295–302. doi:10.4153/CMB-1961-032-6. The manuscript was received by the journal on June 15, 1961. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
• Melzak, Z. A. (September 1961). "An informal Arithmetical Approach to Computability and Computation". Canadian Mathematical Bulletin. 4 (3): 279–293. doi:10.4153/CMB-1961-031-9. The manuscript was received by the journal on May 15, 1961. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
• Minsky, Marvin (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
• Minsky, Marvin (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
• John C. Shepherdson and H. E. Sturgis (1961) received December 1961 "Computability of Recursive Functions", Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".
• Kaphengst, Heinz, "Eine Abstrakte programmgesteuerte Rechenmaschine", Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (1959), 366-379.
• Ershov, A. P. "On operator algorithms", (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
• Péter, Rózsa "Graphschemata und rekursive Funktionen", Dialectica 12 (1958), 373.
• Hermes, Hans "Die Universalität programmgesteuerter Rechenmaschinen". Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42-53.
• Arnold Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. Storage Modification Machines, in Theoretical Computer Science (1979), pp. 36–37
• Peter van Emde Boas, "Machine Models and Simulations" pp. 3–66, in: Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990. van Emde Boas' treatment of SMMs appears on pp. 32–35. This treatment clarifies Schōnhage 1980—it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
• Hao Wang (1957), "A Variant to Turing's Theory of Computing Machines", JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.

• Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. pp. 97-102. ISBN 1-57955-008-8.

बाहरी संबंध

• Weisstein, Eric W. "Register machine". MathWorld.
• Igblan - Minsky Register Machines