सूचक यंत्र

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

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

पॉइंटर मशीनें सामान्य उपायों से अंकगणित नहीं कर सकतीं है। गणना केवल इनपुट प्रतीकों को पढ़ने, संशोधित करने एवं इसकी भंडारण संरचना पर विभिन्न परीक्षण करने - नोड्स एवं पॉइंटर्स के पैटर्न, एवं परीक्षणों के आधार पर प्रतीकों को आउटपुट करने से अग्रसर होती है। सूचना भंडारण संरचना में है.

पॉइंटर मशीनों के प्रकार

गुरेविच एवं बेन-अम्राम दोनों ने अमूर्त मशीनों के कई समान परमाणु मॉडलों की सूची बनाई है; बेन-अम्राम का मानना ​​है कि 6 परमाणु मॉडल को उच्च-स्तरीय मॉडल से भिन्न किया जाना चाहिए। यह लेख विशेष रूप से निम्नलिखित 3 परमाणु मॉडलों पर चर्चा करेगा:

• शॉनहेज की भंडारण संशोधन मशीनें (एसएमएम),
• कोलमोगोरोव-उसपेन्स्की मशीनें (KUM या KU-मशीनें),
• नथ का लिंकिंग ऑटोमेटन

किन्तु बेन-अम्राम जोड़ता है:

• परमाणु शुद्ध-एलआईएसपी मशीन (एपीएलएम)
• परमाणु पूर्ण-एलआईएसपी मशीन (एएफएलएम),
• सामान्य परमाणु सूचक मशीनें,
• जोन की भाषा (दो प्रकार)

पॉइंटर-मशीन मॉडल के साथ समस्याएं

समष्टिता सिद्धांत में मॉडल का उपयोग: वैन एम्डे बोस (1990) चिंता व्यक्त करते हैं कि अमूर्त मॉडल का यह रूप है:

दिलचस्प सैद्धांतिक मॉडल, किन्तु ... समष्टिता सिद्धांत के लिए मौलिक मॉडल के रूप में इसका आकर्षण संदिग्ध है। इसका समय माप ऐसे संदर्भ में समान समय पर आधारित है जहां यह माप वास्तविक समय समष्टिता को कम आंकने के लिए जाना जाता है। मशीन के लिए स्थान माप के लिए भी यही अवलोकन प्रस्तावित होता है (वैन एम्डे बोस (1990) पृष्ठ 35)

गुरेविच 1988 भी चिंता व्यक्त करते हैं:

व्यावहारिक रूप से कहें तो, शॉनहेज मॉडल कला की वर्तमान स्थिति में समय की समष्टिता का उत्तम माप प्रदान करता है (चूँकि मैं एंग्लुइन एवं वैलेंट के रैंडम ्सेस कंप्यूटर की तर्ज पर कुछ पसंद करूंगा) (गुरेविच (1988) पृष्ठ 6 एंग्लुइन डी एवं वैलेंट एल.जी. के संदर्भ में, हैमिल्टनियन सर्किट एवं मिलान के लिए फास्ट प्रोबेबिलिस्टिक एल्गोरिदम, जर्नल ऑफ कंप्यूटर एंड सिस्टम साइंसेज 18 (1979) ) 155-193.)

तथ्य यह है कि, §3 एवं §4 (पीपी. 494-497) में, शॉनहेज स्वयं (1980) अपने दो रैंडम-्सेस मशीन मॉडल RAM0 एवं RAM1 की वास्तविक समय तुल्यता को प्रदर्शित करता है, जो समष्टिता अध्ययन के लिए SMM की आवश्यकता पर सवाल उठाता है।

मॉडल के लिए संभावित उपयोग: हालाँकि, शॉनहेज (1980) अपने §6, रैखिक समय में पूर्णांक-गुणन में प्रदर्शित करता है। एवं गुरेविच को आश्चर्य है कि समानांतर केयू मशीन कुछ हद तक मानव मस्तिष्क से मिलती जुलती है या नहीं (गुरेविच (1988) पृष्ठ 5)

शॉनहेज की भंडारण संशोधन मशीन (एसएमएम) मॉडल

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

वर्णमाला के प्रतीकों के प्रत्येक शब्द को मशीन के माध्यम से मार्ग में अनुवादित किया जा सकता है; उदाहरण के लिए, 10011 प्रारंभ नोड से पथ 1, फिर परिणामी नोड से पथ 0, फिर पथ 0, फिर पथ 1, फिर पथ 1 लेने में अनुवादित होगा। पथ, बदले में, परिणामी नोड से पहचाना जा सकता है, किन्तु गणना के दौरान ग्राफ़ बदलते ही यह पहचान बदल जाएगी।

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

2-प्रतीक {0,1} मशीन में नए नोड के निर्माण के चरण: जब उपन्यास शब्द (यहां: 11) के साथ सामना किया जाता है, तो मशीन जिम्मेदार होती है (i) नया नोड 3 बनाना एवं उस पर उपयुक्त 1-किनारे को इंगित करना, फिर (ii) दो नए पॉइंटर्स बनाना ( 0-किनारे एवं 1-किनारे) जो दोनों पूर्व नोड पर वापस इंगित करते हैं (यहां: नोड 2)।

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

• उदाहरण: मान लीजिए w 10110[1] है, जहां अंतिम वर्ण इसकी विशेष स्थिति को दर्शाने के लिए कोष्ठक में है। हम 10110 तक पहुंचने वाले नोड के 1 किनारे को लेते हैं (पांच-किनारे के अंत में, इसलिए छह-नोड, मार्ग), एवं इसे नए 7वें नोड पर इंगित करते हैं। इस नए नोड के दो किनारे फिर पथ के छठे नोड की ओर पीछे की ओर इंगित करते हैं।

(2) w को v पर सेट करें: w शब्द द्वारा दर्शाए गए पथ से किनारे (तीर) को पूर्व नोड पर रीडायरेक्ट (स्थानांतरित) करता है जो v शब्द का प्रतिनिधित्व करता है। पुनः यह पथ का अंतिम तीर है जिसे पुनर्निर्देशित किया गया है।

• उदाहरण: उपरोक्त निर्देश के बाद 1011011 को 1011 पर सेट करें, 101101 पर नए नोड के 1 तीर को बदलकर 1011 पर पहुंचने वाले मार्ग में पांचवें नोड को इंगित करेगा। इस प्रकार पथ 1011011 का परिणाम अब 1011 जैसा ही होगा।

(3) यदि v = w तो निर्देश z: सशर्त निर्देश जो w एवं v शब्दों द्वारा दर्शाए गए दो पथों की तुलना करता है यह देखने के लिए कि क्या वे ही नोड पर समाप्त होते हैं; यदि ऐसा है तो अनुदेश z पर जाएं अन्यथा जारी रखें। यह निर्देश रजिस्टर मशीन या वांग बी-मशीन में अपने समकक्ष के समान उद्देश्य को पूरा करता है, जो ट्यूरिंग मशीन की नई स्थिति में जाने की क्षमता के अनुरूप है।

2-प्रतीक {0,1} मशीन में नए नोड्स के निर्माण के चरण। जैसे ही शब्द - प्रतीक 0 एवं 1 की स्ट्रिंग - मशीन में आते हैं, मशीन ग्राफ़ बनाती है। जैसा कि यहां दिखाया गया है, 5वें चरण के बाद दो शब्द - 111 एवं 10 - दोनों नोड 4 की ओर इशारा करते हैं। इस समय, यदि मशीन को यदि 10=111 तो xxx करना है, तो परीक्षण सफल होगा एवं मशीन वास्तव में xxx पर पहुंच जाएगा।

नथ का लिंकिंग ऑटोमेटन मॉडल

स्कोनहेज के अनुसार, नुथ ने कहा कि एसएमएम मॉडल विशेष प्रकार के लिंकिंग ऑटोमेटा से मेल खाता है जिसे कंप्यूटर प्रोग्रामिंग की कला के खंड में संक्षेप में समझाया गया है (सीएफ. [4, पीपी. 462-463])

कोलमोगोरोव-उसपेन्स्की मशीन (केयू-मशीन) मॉडल

KUM केवल उलटे पॉइंटर्स की अनुमति देने में SMM से भिन्न है: नोड x से नोड y तक प्रत्येक पॉइंटर के लिए, y से x तक व्युत्क्रम पॉइंटर उपस्थित होना चाहिए। चूँकि आउटगोइंग पॉइंटर्स को वर्णमाला के भिन्न-भिन्न प्रतीकों द्वारा लेबल किया जाना चाहिए, KUM एवं SMM दोनों ग्राफ़ में O(1) आउटडिग्री है। हालाँकि, KUM पॉइंटर्स की व्युत्क्रमता इन-डिग्री को O(1) तक भी सीमित करती है। यह भौतिक (विशुद्ध रूप से सूचनात्मक के विपरीत) यथार्थवाद के लिए कुछ चिंताओं को संबोधित करता है, जैसे उपरोक्त वैन एम्डे बोस उद्धरण में।

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

यह भी देखें

रजिस्टर मशीन-जेनेरिक रजिस्टर-आधारित अमूर्त मशीन कम्प्यूटेशनल मॉडल

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

ट्यूरिंग मशीन-जेनेरिक टेप-आधारित अमूर्त मशीन कम्प्यूटेशनल मॉडल

• पोस्ट-ट्यूरिंग मशीन-न्यूनतम -टेप, दो-दिशा, 1 प्रतीक {रिक्त, चिह्न} ट्यूरिंग जैसी मशीन किन्तु मूल 3-निर्देश काउंटर मशीनों के समान डिफ़ॉल्ट अनुक्रमिक निर्देश निष्पादन के साथ।

संदर्भ

Most references and a bibliography are to be found at the article Register machine. The following are particular to this article:

• Amir Ben-Amram (1995), What is a "Pointer machine"?, SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volume 26, 1995. also: DIKU, Department of Computer Science, University of Copenhagen, amirben@diku.dk. Wherein Ben-Amram describes the types and subtypes: (type 1a) Abstract Machines: Atomistic models including Kolmogorov-Uspenskii Machines (KUM), Schönhage's Storage Modification Machines (SMM), Knuth's "Linking Automaton", APLM and AFLM (Atomistic Pure-LISP Machine) and (Atomistic Full-LISP machine), General atomistic Pointer Machines, Jone's I Language; (type 1b) Abstract Machines: High-level models, (type 2) Pointer algorithms.
• Andrey Kolmogorov and V. Uspenskii, On the definition of an algorithm, Uspekhi Mat. Nauk 13 (1958), 3-28. English translation in American Mathematical Society Translations, Series II, Volume 29 (1963), pp. 217–245.
• Yuri Gurevich (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, no. 1, (July 2000), pages 77–111. In a single sentence Gurevich compares the Schönhage [1980] "storage modification machines" to Knuth's "pointer machines." For more, similar models such as "random access machines" Gurevich references:
  • John E. Savage (1998), Models of Computation: Exploring the Power of Computing. Addison Wesley Longman.
• Yuri Gurevich (1988), On Kolmogorov Machines and Related Issues, the column on "Logic in Computer Science", Bulletin of European Association for Theoretical Computer Science, Number 35, June 1988, 71-82. Introduced the unified description of Schönhage and Kolmogorov-Uspenskii machines used here.
• 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. He refers to an earlier paper where he introduces the SMM:
  • Arnold Schönhage (1970), Universelle Turing Speicherung, Automatentheorie und Formale Sprachen, Dörr, Hotz, eds. Bibliogr. Institut, Mannheim, 1970, pp. 69–383.
• Peter van Emde Boas, Machine Models and Simulations pp. 3–66, appearing 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.