मूर मशीन

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

फॉर्मल डेफिनिशन

मूर मशीन को निम्नलिखित से मिलकर 6-टुपल $(S,s_{0},\Sigma ,O,\delta ,G)$ के रूप में डिफाइन किया जा सकता है:

• स्टेट $S$ का एक फाईनाईट सेट (कंप्यूटर विज्ञान)
• एक स्टार्ट स्टेट $s_{0}$ (जिसे स्टार्ट स्टेट भी कहा जाता है) जो कि $S$ का एक एलिमेंट है
• एक फाईनाईट सेट जिसे इनपुट अल्फाबेट (कंप्यूटर विज्ञान) $\Sigma$ कहा जाता है
• एक फाईनाईट सेट जिसे आउटपुट अल्फाबेट (कंप्यूटर विज्ञान) $O$ कहा जाता है
• एक ट्रांजीशन फलन (गणित) $\delta :S\times \Sigma \rightarrow S$ एक स्टेट और इनपुट अल्फाबेट को अगले स्टेट में मैप करना
• एक आउटपुट फ़ंक्शन $G:S\rightarrow O$ प्रत्येक स्टेट को आउटपुट अल्फाबेट में मैप करना

मूर मशीन को एक रिस्ट्रिक्टेड टाइप के फाईनाईट-स्टेट ट्रांसड्यूसर के रूप में माना जा सकता है।

विसुअल रिप्रजेंटेशन

टेबल

स्टेट ट्रांजीशन टेबल एक टेबल है जो ट्रांजीशन रिलेशनशिप में सभी ट्रिपल्स $\delta :S\times \Sigma \rightarrow S$ को सूचीबद्ध करती है।

डायग्राम

मूर मशीन के लिए स्टेट डायग्राम, या मूर डायग्राम, एक डायग्राम स्टेट डायग्राम है जो प्रत्येक स्टेट के साथ एक आउटपुट वैल्यू को जोड़ता है।

मीली मशीनों से रिलेशनशिप

चूँकि मूर और मीली मशीनें दोनों टाइप की फाईनाईट-स्टेट मशीनें हैं, वे समान रूप से एक्सप्रेसिव हैं: किसी भी टाइप का उपयोग रेगुलर लैंग्वेज को पार्स करने के लिए किया जा सकता है।

मूर मशीनों और मीली मशीनों के बीच अंतर यह है कि बाद में, एक ट्रांजीशन का आउटपुट करंट स्टेट (कंप्यूटर विज्ञान) और करंट इनपुट के कॉम्बिनेशन से निर्धारित होता है ($S\times \Sigma$ के डोमेन के रूप में $G$), करंट स्टेट के विपरीत ($S$ के डोमेन के रूप में $G$)। जब एक स्टेट डायग्राम के रूप में दर्शाया जाता है,

• मूर मशीन के लिए, प्रत्येक नोड (स्टेट) को आउटपुट वैल्यू के साथ लेबल किया जाता है;
• मीली मशीन के लिए, प्रत्येक आर्क (ट्रांजीशन) को आउटपुट वैल्यू के साथ लेबल किया जाता है।

प्रत्येक मूर मशीन $M$ समान स्टेट और ट्रांजीशन और आउटपुट फ़ंक्शन वाली मीली मशीन $G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))$ के समतुल्य है, जो प्रत्येक स्टेट-इनपुट जोड़ी $(s,\sigma )$ लेता है और $G_{M}(\delta _{M}(s,\sigma ))$ यील्ड करता है, जहाँ $G_{M}$ $M$ का आउटपुट फ़ंक्शन है और $\delta _{M}$ $M$ का ट्रांजीशन फ़ंक्शन है।

हालाँकि, प्रत्येक मीली मशीन को समकक्ष मूर मशीन में कन्वर्ट नहीं किया जा सकता है। कुछ को केवल लगभग समकक्ष मूर मशीन में कन्वर्ट किया जा सकता है, जिसमें आउटपुट टाइम पर शिफ्ट हो जाते हैं। यह उस तरीके के कारण है जिसमें इनपुट/आउटपुट जोड़े बनाने के लिए स्टेट लेबल को ट्रांजीशन लेबल के साथ जोड़ा जाता है। एक ट्रांजीशन पर विचार करें $s_{i}\rightarrow s_{j}$ $s_{i}$ स्टेट से $s_{j}$ स्टेट तक। ट्रांजीशन का कारण बनने वाला इनपुट $s_{i}\rightarrow s_{j}$ एज $(s_{i},s_{j})$ को लेबल करता है। उस इनपुट के अनुरूप आउटपुट, स्टेट $s_{i}$ का लेबल है। ध्यान दें कि यह ट्रांजीशन की सोर्स स्टेट है। इसलिए प्रत्येक इनपुट के लिए, आउटपुट इनपुट प्राप्त होने से पहले ही फिक्स हो जाता है, और पूरी तरह से करंट स्टेट पर निर्भर करता है। यह ई. मूर की ओरिजिनल डेफिनिशन है। स्टेट के लेबल का $s_{j}$ ट्रांजीशन के लिए आउटपुट $s_{i}\rightarrow s_{j}$ के रूप में उपयोग करना एक कॉमन मिस्टेक है।

उदाहरण

इनपुट/आउटपुट की संख्या के अकॉर्डिंग टाइप।

सिंपल

सरल मूर मशीनों में एक इनपुट और एक आउटपुट होता है:

• XOR का उपयोग करके एज डिटेक्ट करना
• बाइनरी अड्डिंग मशीन
• क्लॉक्ड सीक्वेनशीअल सिस्टम (मूर मशीन का एक रिस्ट्रिक्टेड रूप जहां स्टेट केवल तभी बदलती है जब वैश्विक क्लॉक सिग्नल बदलता है)

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

वर्कड एक्साम्पल

सीक्वेनशीअल नेटवर्क में एक इनपुट और एक आउटपुट होता है। आउटपुट 1 हो जाता है और उसके बाद 1 ही रहता है जब इनपुट के रूप में कम से कम दो 0 और दो 1 आए हों।

उपरोक्त डिस्क्रिप्शन के लिए नौ स्टेट वाली एक मूर मशीन दाईं ओर दिखाई गई है। इनिशियल स्टेट A है, और फाइनल स्टेट I है। इस उदाहरण के लिए स्टेट टेबल इस प्रकार है:

करंट स्टेट	इनपुट	नेक्स्ट स्टेट	आउटपुट
A	0	D	0
	1	B
B	0	E	0
	1	C
C	0	F	0
	1	C
D	0	G	0
	1	E
E	0	H	0
	1	F
F	0	I	0
	1	F
G	0	G	0
	1	H
H	0	H	0
	1	I
I	0	I	1
	1	I

कॉम्प्लेक्स

अधिक कॉम्प्लेक्स मूर मशीनों में कई इनपुट के साथ-साथ कई आउटपुट भी हो सकते हैं।

गेडानकेन-प्रयोग

मूर के 1956 के पेपर थॉट गेडैंकेन-एक्सपेरिमेंट्स ऑन सीक्वेंशियल मशीन में, $(n;m;p)$ ऑटोमेटा (या मशीनें) S को N स्टेट, m इनपुट प्रतीकों और P आउटपुट प्रतीकों के रूप में परिभाषित किया गया है। $S$ की संरचना के बारे में नौ प्रमेय सिद्ध हैं, और $S$ के साथ एक्सपेरिमेंट बाद में, $S$ मशीनों को मूर मशीनों के नाम से जाना जाने लगा।

पेपर के अंत में, अनुभाग आगे की प्रॉब्लम में, निम्नलिखित कार्य बताया गया है:

एक और सीधे तौर पर सामने आने वाली प्रॉब्लम प्रमेय 8 और 9 में दी गई सीमाओं में सुधार है।

मूर का प्रमेय 8 इस टाइप तैयार किया गया है:

दिया गया आरबिटरेरी $(n;m;p)$ मशीन $S$, जैसे कि इसकी प्रत्येक दो स्टेट एक दूसरे से भिन्न हों, तब लेंथ का एक एक्सपेरिमेंट ${\tfrac {n(n-1)}{2}}$ उपस्थित होता है जो की $S$ प्रयोग के अंत में स्टेट निर्धारित करता है।

1957 में, अनातोली अलेक्सेविच करात्सुबा|ए. ए. करात्सुबा ने निम्नलिखित दो थ्योरम को प्रूव किया, जिससे उनके प्रमेय 8 की एक्सपेरिमेंट लेंथ के बाउंड में सुधार पर मूर की प्रॉब्लम पूरी तरह से हल हो गई।

थ्योरम A. यदि $S$ एक $(n;m;p)$ मशीन, इस टाइप कि उसकी प्रत्येक दो स्टेट एक-दूसरे से भिन्न होती हैं, तो अधिकतम लेंथ का एक ब्रान्च्ड एक्सपेरिमेंट ${\tfrac {(n-1)(n-2)}{2}}+1$ उपस्थित होता है जिसके माध्यम से प्रयोग के अंत में कोई भी $S$ की स्टेट का निर्धारण कर सकता है।

थ्योरम B. वहाँ एक $(n;m;p)$ मशीन उपस्थित है, प्रत्येक दो स्टेट एक दूसरे से भिन्न होती हैं, जैसे कि प्रयोग के अंत में मशीन की स्टेट स्थापित करने वाले सबसे छोटे एक्सपेरिमेंट ${\tfrac {(n-1)(n-2)}{2}}+1$ की लेंथ बराबर होती है।

प्रमेय ए और बी का उपयोग ऑटोमेटा थ्योरी की एक प्रॉब्लम पर चौथे वर्ष के छात्र ए.ए. करात्सुबा के कोर्स वर्क के आधार पर किया गया था, जिसे 1958 में मॉस्को स्टेट यूनिवर्सिटी के मैकेनिक्स और मैथमेटिक्स के छात्र कार्यों की कॉम्पीटीशन में टेस्टीमोनियल रिफरेन्स द्वारा प्रतिष्ठित किया गया था। करात्सुबा का पेपर 17 दिसंबर 1958 को उसपेखी मैट नौक पत्रिका को दिया गया था और जून 1960 में वहां पब्लिश हुआ।

प्रेजेंट डे (2011) तक, एक्सपेरिमेंट की लेंथ पर करात्सुबा का परिणाम एकमात्र सटीक नॉनलीनिअर रिजल्ट है, ऑटोमेटा सिद्धांत और कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी की समान प्रॉब्लम में है।

यह भी देखें

• सिंक्रोनस सर्किट
• मैली मशीन
• एल्गोरिथम स्टेट मशीन
• स्वायत्त प्रणाली (गणित)

अग्रिम पठन

• Conway, J.H. (1971). Regular algebra and finite machines. London: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041.
• Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.(1956).
• Karatsuba A. A. Solution of one problem from the theory of finite automata. Usp. Mat. Nauk, 15:3, 157–159 (1960).
• Karatsuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).
• Karatsuba A. A. List of research works.

Moore-and-Mealy-Machine

बाहरी रिलेशनशिप

• Media related to मूर मशीन at Wikimedia Commons