मूर मशीन

गणना के सिद्धांत में, मूर मशीन एक परिमित-राज्य मशीन है जिसका वर्तमान आउटपुट मान केवल इसकी वर्तमान स्थिति (कंप्यूटर विज्ञान) द्वारा निर्धारित किया जाता है। यह एक मैली मशीन के विपरीत है, जिसका आउटपुट मूल्य इसकी वर्तमान स्थिति और इसके इनपुट के मूल्यों दोनों द्वारा निर्धारित किया जाता है। अन्य परिमित अवस्था मशीनों की तरह, मूर मशीनों में, इनपुट आमतौर पर अगली अवस्था को प्रभावित करता है। इस प्रकार इनपुट अप्रत्यक्ष रूप से बाद के आउटपुट को प्रभावित कर सकता है, लेकिन वर्तमान या तत्काल आउटपुट को नहीं। मूर मशीन का नाम एडवर्ड एफ. मूर के नाम पर रखा गया है, जिन्होंने 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 का उपयोग करके किनारे का पता लगाना
• विकिपुस्तकें:फ्रैक्टल्स/गणित/समूह/बाइनरी जोड़ने वाली मशीन
• क्लॉक्ड अनुक्रमिक प्रणाली#क्लॉक्ड अनुक्रमिक सिस्टम (मूर मशीन का एक प्रतिबंधित रूप जहां स्थिति केवल तभी बदलती है जब वैश्विक घड़ी सिग्नल बदलता है)

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

कार्य उदाहरण

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

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

Current state	Input	Next state	Output
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 की प्रयोग लंबाई की सीमा में सुधार पर मूर की समस्या पूरी तरह से हल हो गई।

<ब्लॉककोट>प्रमेय ए. यदि $S$ एक $(n;m;p)$ मशीन, इस प्रकार कि उसकी प्रत्येक दो अवस्थाएँ एक-दूसरे से भिन्न होती हैं, तो अधिकतम लंबाई का एक शाखित प्रयोग मौजूद होता है ${\tfrac {(n-1)(n-2)}{2}}+1$ जिसके माध्यम से कोई भी व्यक्ति की स्थिति का निर्धारण कर सकता है $S$ प्रयोग के अंत में. <ब्लॉककोट>प्रमेय बी. वहाँ एक मौजूद है $(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