टैग प्रणाली

गणना के सिद्धांत में, एक टैग सिस्टम 1943 में एमिल लियोन पोस्ट द्वारा पोस्ट विहित प्रणाली के एक सरल रूप के रूप में प्रकाशित गणना का एक नियतात्मक मॉडल है।^[1] एक टैग सिस्टम को एक अमूर्त मशीन के रूप में भी देखा जा सकता है, जिसे पोस्ट टैग मशीन कहा जाता है (पोस्ट-ट्यूरिंग मशीन के साथ भ्रमित नहीं होना चाहिए|पोस्ट-ट्यूरिंग मशीन) - संक्षेप में, एक परिमित-राज्य मशीन जिसका एकमात्र टेप FIFO (कंप्यूटिंग) है और इलेक्ट्रॉनिक्स) असीमित लंबाई की कतार (डेटा संरचना), जैसे कि प्रत्येक संक्रमण में मशीन कतार के शीर्ष पर प्रतीक को पढ़ती है, सिर से प्रतीकों की निरंतर संख्या को हटा देती है, और पूंछ पर एक प्रतीक-स्ट्रिंग जोड़ती है जो निर्भर करती है केवल इस संक्रमण में पढ़े गए पहले प्रतीक पर।

क्योंकि सभी संकेतित ऑपरेशन एक ही संक्रमण में किए जाते हैं, एक टैग मशीन में सख्ती से केवल एक ही स्थिति होती है।

परिभाषाएँ

एक टैग प्रणाली एक त्रिक (एम, ए, पी) है, जहां

m एक धनात्मक पूर्णांक है, जिसे विलोपन संख्या कहा जाता है।
ए प्रतीकों की एक सीमित वर्णमाला है, जिनमें से एक विशेष रुकने वाला प्रतीक हो सकता है। A पर सभी परिमित (संभवतः खाली) तारों को शब्द कहा जाता है।
P उत्पादन नियमों का एक सेट है, जो A में प्रत्येक प्रतीक x के लिए एक शब्द P(x) (जिसे उत्पादन कहा जाता है) निर्दिष्ट करता है। उत्पादन (मान लीजिए P(H)) गणना में कोई भूमिका नहीं निभाने के लिए नीचे दिए गए रुकने के प्रतीक को देखा गया है, लेकिन सुविधा के लिए इसे P माना गया है(H) ='H'.

रुकने वाला शब्द वह शब्द है जो या तो रुकने वाले चिन्ह से शुरू होता है या जिसकी लंबाई m से कम होती है।

एक परिवर्तन t (जिसे टैग ऑपरेशन कहा जाता है) को गैर-रुकने वाले शब्दों के सेट पर परिभाषित किया गया है, जैसे कि यदि x किसी शब्द S के सबसे बाएं प्रतीक को दर्शाता है, तो t(S) S के सबसे बाएं m प्रतीकों को हटाने का परिणाम है और दाईं ओर P(x) शब्द जोड़ना। इस प्रकार, सिस्टम एम-प्रतीक सिर को परिवर्तनीय लंबाई की पूंछ में संसाधित करता है, लेकिन उत्पन्न पूंछ पूरी तरह से सिर के पहले प्रतीक पर निर्भर करती है।

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

एम-टैग सिस्टम शब्द का प्रयोग अक्सर विलोपन संख्या पर जोर देने के लिए किया जाता है। साहित्य में परिभाषाएँ कुछ भिन्न होती हैं (cf. सन्दर्भ), जो यहाँ प्रस्तुत है वह रोगोज़िन की है।^[2]

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

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

उदाहरण: एक सरल 2-टैग चित्रण

यह केवल एक सरल 2-टैग प्रणाली को चित्रित करने के लिए है जो रुकने के प्रतीक का उपयोग करता है।

<पूर्व> 2-टैग प्रणाली

   वर्णमाला: {ए,बी,सी,एच}
   उत्पादन नियम:
        ए --> सीसीबीएएच
        बी --> सीसीए
        सी --> सीसी

गणना

   प्रारंभिक शब्द: बा
                   एसीसीए
                     caccbaH
                       ccbaHcc
                         baHcccc
                           एचसीसीसीसीसीए (रोकें)।

</पूर्व>

उदाहरण: Collatz अनुक्रमों की गणना

इस सरल 2-टैग प्रणाली से अनुकूलित किया गया है De Mol (2008). यह किसी रुकने के प्रतीक का उपयोग नहीं करता है, लेकिन 2 से कम लंबाई वाले किसी भी शब्द पर रुकता है, और Collatz अनुमान के थोड़े संशोधित संस्करण की गणना करता है।

मूल Collatz अनुक्रम में, n का उत्तराधिकारी या तो है n/2 (सम n के लिए) या 3n + 1 (विषम n के लिए)। विषम n के लिए मान 3n + 1 स्पष्ट रूप से सम है, इसलिए 3n + 1 के बाद अगला पद निश्चित रूप से है 3n + 1/2. नीचे टैग सिस्टम द्वारा गणना किए गए अनुक्रम में हम इस मध्यवर्ती चरण को छोड़ देते हैं, इसलिए n का उत्तराधिकारी है 3n + 1/2 विषम n के लिए।

इस टैग प्रणाली में, एक धनात्मक पूर्णांक n को n a के साथ aa...a शब्द द्वारा दर्शाया जाता है।

<पूर्व> 2-टैग प्रणाली

   वर्णमाला: {ए,बी,सी}
   उत्पादन नियम:
        ए --> बी.सी
        बी -> ए
        सी --> आआ

गणना

   प्रारंभिक शब्द: आआ <--> एन=3
                   एबीसी
                     सीबीसी
                       caaa
                         आआआ <-->
                           aaabc
                             abcbc
                               सीबीसीबीसी
                                 सीबीसीएएए
                                   काआआ
                                     आआआआआ <-->
                                       आआआआआआआएबीसी
                                         aaaabcbc
                                           aabcbcbc
                                             bcbcbcbc
                                               bcbcbca
                                                 bcbcaa
                                                   bcaaa
                                                     आआआ <-->
                                                       aabc
                                                         बीबीसीसी समाचार
                                                           बीसीए
                                                             आ <-->
                                                               ईसा पूर्व
                                                                 एक <-->
                                                                  (रुको)

</पूर्व>

एम-टैग सिस्टम की ट्यूरिंग-पूर्णता

प्रत्येक एम > 1 के लिए, एम-टैग सिस्टम का सेट ट्यूरिंग पूर्णता है|ट्यूरिंग-पूर्ण; यानी, प्रत्येक एम > 1 के लिए, यह मामला है कि किसी भी ट्यूरिंग मशीन 'टी' के लिए, एक एम-टैग प्रणाली है जो सरोगेट मॉडल 'टी' है। विशेष रूप से, यूनिवर्सल ट्यूरिंग मशीन का अनुकरण करने के लिए 2-टैग सिस्टम का निर्माण किया जा सकता है, जैसा कि किया गया था Wang (1963) और तक Cocke & Minsky (1964).

इसके विपरीत, एक ट्यूरिंग मशीन को यह साबित करके एक यूनिवर्सल ट्यूरिंग मशीन के रूप में दिखाया जा सकता है कि यह एम-टैग सिस्टम के ट्यूरिंग-पूर्ण वर्ग का अनुकरण कर सकती है। उदाहरण के लिए, Rogozhin (1996) वर्णमाला के साथ 2-टैग सिस्टम के वर्ग की सार्वभौमिकता साबित हुई {ए₁, ..., ए_n, H} और संबंधित उत्पादन {ए_na_nW₁, ..., ए_na_nW_n-1, ए_na_n, H}, जहां डब्ल्यू_kगैर-रिक्त शब्द हैं; इसके बाद उन्होंने एक बहुत छोटी (4-राज्य, 6-प्रतीक) ट्यूरिंग मशीन की सार्वभौमिकता साबित की, यह दिखाकर कि यह टैग सिस्टम के इस वर्ग का अनुकरण कर सकती है।

2-टैग प्रणाली सार्वभौमिक ट्यूरिंग मशीनों का एक कुशल सिम्युलेटर है $O(t^{4}\ln ^{2}t)$ समय। अर्थात यदि $M$ एक नियतात्मक एकल-टेप ट्यूरिंग मशीन है जो समय के अनुसार चलती है $t$ , फिर एक 2-टैग प्रणाली है जो इसे अनुकरण करती है $O(t^{4}\ln ^{2}t)$ समय।^[3]

2-टैग रुकने की समस्या

रुकने की समस्या का यह संस्करण सबसे सरल, सबसे आसानी से वर्णित अनिर्णीत समस्या निर्णय समस्याओं में से एक है:

एक मनमाना सकारात्मक पूर्णांक n और n+1 मनमाना शब्द P की एक सूची दी गई है₁,पी₂,...,पी_n,Q वर्णमाला {1,2,...,n} पर, टैग ऑपरेशन t का बार-बार अनुप्रयोग करता है: ijX → XP_i अंततः Q को 2 से कम लंबाई वाले शब्द में परिवर्तित करें? अर्थात् अनुक्रम Q, t करता है¹(Q), t²(Q), t³(Q), ...समाप्त करें?

टैग सिस्टम की परिभाषा पर ऐतिहासिक नोट

उपरोक्त परिभाषा इससे भिन्न है Post (1943), जिनके टैग सिस्टम किसी हॉल्टिंग प्रतीक का उपयोग नहीं करते हैं, बल्कि केवल खाली शब्द पर रुकते हैं, टैग ऑपरेशन टी को इस प्रकार परिभाषित किया गया है:

यदि x एक गैर-रिक्त शब्द S के सबसे बाएं प्रतीक को दर्शाता है, तो t(S) वह ऑपरेशन है जिसमें पहले शब्द P(x) को S के दाएं छोर पर जोड़ना होता है, और फिर परिणाम के सबसे बाएं m प्रतीकों को हटाना - यदि m से कम प्रतीक हैं तो सभी को हटाना।

किसी भी एम > 1 के लिए एम-टैग सिस्टम के सेट की ट्यूरिंग-पूर्णता से संबंधित उपरोक्त टिप्पणी, इन टैग सिस्टम पर भी लागू होती है जैसा कि मूल रूप से पोस्ट द्वारा परिभाषित किया गया है।

नाम टैग की उत्पत्ति

में एक फुटनोट के अनुसार Post (1943), बी. पी. गिल ने समस्या के पहले संस्करण के लिए नाम सुझाया जिसमें पहले एम प्रतीकों को अछूता छोड़ दिया गया है, बल्कि वर्तमान स्थिति को इंगित करने वाला एक चेक मार्क हर कदम पर एम प्रतीकों द्वारा दाईं ओर चला जाता है। यह निर्धारित करने की समस्या का नाम कि क्या चेक मार्क कभी अनुक्रम के अंत को छूता है या नहीं, तब बच्चों के टैग (खेल) का जिक्र करते हुए टैग की समस्या करार दिया गया था।

चक्रीय टैग सिस्टम

चक्रीय टैग प्रणाली मूल टैग प्रणाली का एक संशोधन है। वर्णमाला में केवल दो प्रतीक होते हैं, 0 और 1, और उत्पादन नियमों में क्रमिक रूप से विचार किए जाने वाले उत्पादनों की एक सूची शामिल होती है, जो सूची में अंतिम उत्पादन पर विचार करने के बाद सूची की शुरुआत में वापस आती है। प्रत्येक उत्पादन के लिए, शब्द के सबसे बाएं प्रतीक की जांच की जाती है - यदि प्रतीक 1 है, तो वर्तमान उत्पादन शब्द के दाहिने छोर से जोड़ा जाता है; यदि प्रतीक 0 है, तो शब्द में कोई वर्ण नहीं जोड़ा जाता है; किसी भी स्थिति में, सबसे बायां प्रतीक हटा दिया जाता है। जब शब्द खाली हो जाता है तो सिस्टम रुक जाता है।^[4]

उदाहरण

<पूर्व> चक्रीय टैग प्रणाली

प्रोडक्शंस: (010,000, 1111)

गणना

प्रारंभिक शब्द: 11001
   उत्पादन शब्द
   --------------
      010 11001
      000 1001010
      1111 001010000
      010 01010000
      000 1010000
      1111 010000000
      010 10000000
       . .
       . .

</पूर्व>

चक्रीय टैग सिस्टम मैथ्यू कुक द्वारा बनाए गए थे और कुक के प्रदर्शन में उपयोग किए गए थे कि नियम 110 सार्वभौमिक है।^[5] प्रदर्शन का एक महत्वपूर्ण हिस्सा यह था कि चक्रीय टैग सिस्टम टैग सिस्टम के ट्यूरिंग-पूर्ण वर्ग का अनुकरण कर सकते हैं।

चक्रीय टैग सिस्टम द्वारा टैग सिस्टम का अनुकरण

वर्णमाला {ए के साथ एक एम-टैग प्रणाली₁, ..., ए_n} और संबंधित प्रस्तुतियां {पी₁, ..., पी_n} एम*एन प्रोडक्शंस (क्यू) के साथ एक चक्रीय टैग प्रणाली द्वारा अनुकरण किया जाता है₁, ..., क्यू_n, -, -, ..., -), जहां पहले एन प्रोडक्शन को छोड़कर सभी खाली स्ट्रिंग हैं (' द्वारा चिह्नित)-'). एकसवाल_kसंबंधित पी के एन्कोडिंग हैं_k, टैग सिस्टम वर्णमाला के प्रत्येक प्रतीक को लंबाई-एन बाइनरी स्ट्रिंग द्वारा निम्नानुसार प्रतिस्थापित करके प्राप्त किया जाता है (इन्हें टैग सिस्टम गणना के प्रारंभिक शब्द पर भी लागू किया जाना है):

ए₁= 100...00
ए₂= 010...00
.
.
.
ए_n= 000...01

वह_kके साथ बाइनरी स्ट्रिंग के रूप में एन्कोड किया गया है 1 के में^{बाएँ से वें}स्थिति, और 0 अन्यत्र. टैग सिस्टम गणना की क्रमिक पंक्तियाँ तब प्रत्येक (m*n) के रूप में एन्कोड की जाएंगी^{चक्रीय टैग प्रणाली द्वारा इसके अनुकरण की पंक्ति।}

उदाहरण

अनुकरण तकनीक को दर्शाने के लिए यह एक बहुत छोटा उदाहरण है। <पूर्व> 2-टैग प्रणाली

   उत्पादन नियम: (ए --> बी बी, बी --> एबीएच, एच --> एच)
   वर्णमाला एन्कोडिंग: ए = 100, बी = 010, एच = 001
   उत्पादन एन्कोडिंग: (बीबी = 010 010, एबीएच = 100 010 001, एच = 001)

चक्रीय टैग प्रणाली

   प्रोडक्शंस: (010 010, 100 010 001, 001, -, -, -)

टैग सिस्टम गणना

   प्रारंभिक शब्द: बा
                   एबीएच
                     एचबीबी (रोकें)

चक्रीय टैग प्रणाली गणना

   प्रारंभिक शब्द: 010 100 (=ba)

   उत्पादन शब्द
   ----------------------------------------
 * 010 010 010 100 (=बीए)
   100 010 001 10 100
   001 0 100 100 010 001
   - 100 100 010 001
   - 00 100 010 001
   - 0 100 010 001
 * 010 010 100 010 001 (=abH)
   100 010 001 00 010 001 010 010
   001 0 010 001 010 010
   - 010 001 010 010
   - 10 001 010 010
   - 0 001 010 010
 * 010 010 अनुकरणित पड़ाव --> 001 010 010 (=एचबीबी)
   100 010 001 01 010 010
   001 1 010 010
   - 010 010 001
   ... ...

</पूर्व> प्रत्येक छठी पंक्ति ( द्वारा चिह्नित)*') चक्रीय टैग सिस्टम द्वारा उत्पादित, टैग सिस्टम गणना की संबंधित पंक्ति का एन्कोडिंग है, जब तक कि अनुकरणीय पड़ाव नहीं पहुंच जाता।

यह भी देखें

कतार स्वचालित
कॉनवे का जीवन का खेल

↑ Post 1943.
↑ Rogozhin 1996.
↑ Woods, Damien; Neary, Turlough (2009-02-17). "The complexity of small universal Turing machines: A survey". Theoretical Computer Science. Computational Paradigms from Nature. 410 (4): 443–450. doi:10.1016/j.tcs.2008.09.051. ISSN 0304-3975. S2CID 10257004.
↑ In a chapter 14 titled "Very Simple Bases for Computability", Minsky (1967) presents a very readable (and exampled) subsection 14.6 The Problem of "Tag" and Monogenic Canonical Systems (pp. 267–273) (this sub-section is indexed as "tag system"). Minsky relates his frustrating experiences with the general problem: "Post found this (00, 1101) problem "intractable," and so did I, even with the help of a computer." He comments that an "effective way to decide, for any string S, whether this process will ever repeat when started with S" is unknown although a few specific cases have been proven unsolvable. In particular he mentions Cocke's Theorem and Corollary 1964.
↑ Cook 2004.

संदर्भ

Cocke, John; Minsky, Marvin (1964). "Universality of Tag Systems with P=2". Journal of the Association for Computing Machinery. 11: 15–20. doi:10.1145/321203.321206. hdl:1721.1/6107. S2CID 2799125.
Cook, Matthew (2004). "Universality in Elementary Cellular Automata". Complex Systems. 15: 1–40. Archived (PDF) from the original on 28 May 2016.
De Mol, Liesbeth (January 2008). "Tag systems and Collatz-like functions". Theoretical Computer Science. 390 (1): 92–101. doi:10.1016/j.tcs.2007.10.020. hdl:1854/LU-436211.
Minsky, Marvin L. (November 1961). "Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines". Annals of Mathematics. 2. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
Minsky, Marvin L. (1967). Computation: Finite and Infinite Machines. Englewoord Cliffs, N.J.: Prentice–Hall. pp. 267–273. ISBN 978-0131655638. LCCN 67-12342.
Post, Emil (1943). "Formal reductions of the combinatorial decision problem". American Journal of Mathematics. 65 (2): 197–215. doi:10.2307/2371809. JSTOR 2371809. (Tag systems are introduced on p. 203ff.)
Rogozhin, Yurii (20 November 1996). "Small Universal Turing Machines". Theoretical Computer Science. 168 (2): 215–240. doi:10.1016/S0304-3975(96)00077-1.
Wang, Hao (1963). "Tag Systems and Lag Systems". Mathematische Annalen. 152: 65–74. doi:10.1007/BF01343730. S2CID 120383146.

बाहरी संबंध

https://mathworld.wolfram.com/TagSystem.html
https://mathworld.wolfram.com/CyclicTagSystem.html
https://www.wolframscience.com/nks/p95/ (cyclic tag systems)
https://www.wolframscience.com/nks/p669/ (emulation of tag systems)

[FOOTNOTEPost1943-1] Post 1943.

[FOOTNOTERogozhin1996-2] Rogozhin 1996.

[3] Woods, Damien; Neary, Turlough (2009-02-17). "The complexity of small universal Turing machines: A survey". Theoretical Computer Science. Computational Paradigms from Nature. 410 (4): 443–450. doi:10.1016/j.tcs.2008.09.051. ISSN 0304-3975. S2CID 10257004.

[4] In a chapter 14 titled "Very Simple Bases for Computability", Minsky (1967) presents a very readable (and exampled) subsection 14.6 The Problem of "Tag" and Monogenic Canonical Systems (pp. 267–273) (this sub-section is indexed as "tag system"). Minsky relates his frustrating experiences with the general problem: "Post found this (00, 1101) problem "intractable," and so did I, even with the help of a computer." He comments that an "effective way to decide, for any string S, whether this process will ever repeat when started with S" is unknown although a few specific cases have been proven unsolvable. In particular he mentions Cocke's Theorem and Corollary 1964.

[FOOTNOTECook2004-5] Cook 2004.

[1]

[2]

[3]

[4]

[5]

टैग प्रणाली

Contents

परिभाषाएँ

उदाहरण: एक सरल 2-टैग चित्रण

उदाहरण: Collatz अनुक्रमों की गणना

एम-टैग सिस्टम की ट्यूरिंग-पूर्णता

2-टैग रुकने की समस्या

टैग सिस्टम की परिभाषा पर ऐतिहासिक नोट

नाम टैग की उत्पत्ति

चक्रीय टैग सिस्टम

उदाहरण

चक्रीय टैग सिस्टम द्वारा टैग सिस्टम का अनुकरण

उदाहरण

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation menu

Search