फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या
फायरिंग स्क्वाड सिंक्रनाइज़ेशन प्रॉब्लम कंप्यूटर विज्ञान और सेलुलर ऑटोमेटन में समस्या है, जिसमें लक्ष्य सेलुलर ऑटोमेटन को डिजाइन करना है, जो सक्रिय सेल से प्रारम्भ होकर अंततः ऐसी स्थिति तक पहुंचता है, जिसमें सभी सेल एक साथ सक्रिय होती हैं। इसे प्रथम बार 1957 में जॉन माइहिल द्वारा प्रस्तावित किया गया था और 1962 में एडवर्ड एफ. मूर द्वारा (जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिंस्की द्वारा समाधान के साथ) प्रकाशित किया गया था।
स्टेटमेंट प्रॉब्लम
समस्या का नाम वास्तविक दुनिया के फायरिंग दस्तों के साथ सादृश्य से आता है। लक्ष्य नियमों की प्रणाली प्रस्तुत करना है जिसके अनुसार अधिकारी निष्पादन विवरण को फायर करने का आदेश दे सकता है, जिससे उसके सदस्य अपनी राइफलों को साथ में फायर कर सकें।
अधिक औपचारिक रूप से, समस्या सेल्यूलर आटोमेटा से संबंधित है, परिमित राज्य मशीनों की सारणी जिन्हें "सेल" कहा जाता है, पंक्ति में व्यवस्थित होती हैं, जैसे कि प्रत्येक समय चरण पर प्रत्येक मशीन अपने पूर्व राज्य और अपने दो प्रतिवेशीयों के राज्यों के कार्य के रूप में नए राज्य में परिवर्तित हो जाती है। फायरिंग स्क्वाड समस्या के लिए, लाइन में सेलो की सीमित संख्या होती है, और नियम जिसके अनुसार प्रत्येक मशीन आगामी राज्य में संक्रमण करती है, लाइन के आंतरिक सभी सेलो के लिए समान होनी चाहिए, किन्तु दो के संक्रमण कार्य रेखा के अंतिम बिंदुओं को भिन्न-भिन्न होने की अनुमति है, क्योंकि इन दोनों सेलो में से प्रत्येक के दोनों किनारों पर एक प्रतिवेशी विलुप्त है।
प्रत्येक सेल की अवस्थाओं में तीन भिन्न-भिन्न अवस्थाएँ सम्मिलित होती हैं: सक्रिय, शांत और सक्रिय, और संक्रमण कार्य ऐसा होना चाहिए, कि सेल जो शांत है और जिसके प्रतिवेशी शांत हैं वह शांत बनी रहे। प्रारंभ में, समय पर t = 0, सबसे बाईं ओर की सेल (सामान्य) को त्यागकर जो सक्रिय है, सभी अवस्थाएँ शांत हैं। लक्ष्य राज्यों का सेट और संक्रमण फ़ंक्शन को इस प्रकार डिज़ाइन करना है कि, सेलो की रेखा कितनी भी लंबी क्यों न हो, एक समय t उपस्थित होता है,जैसे कि जैसे कि t, प्रत्येक सेल समय t पर फायरिंग अवस्था में परिवर्तित हो जाती है, और इस प्रकार कि कोई भी सेल समय से पूर्व फायरिंग की स्थिति में t से संबंधित नहीं होती है।
समाधान
एफएसएसपी का प्रथम समाधान जॉन मैक्कार्थी (कंप्यूटर वैज्ञानिक) और मार्विन मिन्स्की द्वारा पाया गया था और एडवर्ड एफ मूर द्वारा अनुक्रमिक मशीनों में प्रकाशित किया गया था। उनके समाधान में सैनिकों की पंक्ति के नीचे दो तरंगों का प्रसार सम्मिलित है: तीव्र तरंग और मंद तरंग जो तीन गुना मंद गति से चलती है। तीव्र तरंग रेखा के दूसरे किनारे से उछलती है और केंद्र में मंद तरंग से मिलती है। तत्पश्चात दोनों तरंगें चार तरंगों में विभाजित हो गईं, तीव्र और मंद तरंग केंद्र से किसी भी दिशा में चलती हुई, प्रभावी रूप से रेखा को दो बराबर भागों में विभाजित कर देती है। यह प्रक्रिया तब तक निरंतर रहती है, जब तक कि प्रत्येक विभाजन की लंबाई 1 न हो जाए। इस समय, प्रत्येक सैनिक गोली चलाता है। इस समाधान के लिए n सैनिकों के लिए 3n इकाई समय की आवश्यकता होती है।
न्यूनतम समय का उपयोग करने वाला समाधान (जो n सैनिकों के लिए 2n − 2 इकाई समय है), सर्वप्रथम इइची गोटो (1962) द्वारा शोध किया गया था, किन्तु उसके समाधान में हजारों राज्यों का उपयोग किया गया था। वैक्समैन (1966) इसे 16 राज्यों तक सही किया, और बाल्ज़र (1967) ने इसे आठ राज्यों तक सही किया, जबकि यह प्रमाणित करने का अधिकार किया, कि कोई चार-राज्य समाधान उपस्थित नहीं है। पीटर सैंडर्स (कंप्यूटर वैज्ञानिक) ने पश्चात में पाया कि बाल्ज़र की शोध प्रक्रिया अधूरी थी, किन्तु सही शोध प्रक्रिया के माध्यम से चार-राज्य गैर-अस्तित्व परिणाम की से पुष्टि करने में सफल रहे। वर्तमान में सबसे उत्तम ज्ञात समाधान, छह राज्यों का उपयोग करते हुए जैक्स माज़ोयेर (1987) द्वारा प्रस्तुत किया गया था। यह अभी भी अज्ञात है कि क्या पाँच-राज्य समाधान उपस्थित है।
न्यूनतम समय समाधानों में, सामान्य सही सिग्नल S1, S2, S3, ..., Si को 1, 1/3, 1/7, ..., 1/(2 i−1 − 1) की गति से भेजता है।), सिग्नल S1 लाइन के दाहिने किनारे पर प्रतिबिंबित होता है, और सेल n/2 i−1 पर सिग्नल Si ( i ≥ 2 के लिए) से मिलता है। जब S1 प्रतिबिंबित करता है, तो यह दाएँ किनारे पर नया सामान्य भी बनाता है। सिग्नल Si का निर्माण सहायक संकेतों का उपयोग करके किया जाता है, जो बाईं ओर विस्तृत होता है। प्रत्येक दूसरी बार जब कोई सिग्नल (दाईं ओर) चलता है, तो यह बाईं ओर सहायक सिग्नल भेजता है। S1 अपने आप गति 1 से चलता है, जबकि प्रत्येक मंद सिग्नल केवल तभी चलता है, जब उसे कोई सहायक सिग्नल मिलता है।
सामान्यीकरण
फायरिंग स्क्वाड सिंक्रनाइज़ेशन समस्या को कई अन्य प्रकार के सेलुलर ऑटोमेटन के लिए सामान्यीकृत किया गया है, जिसमें सेलो के उच्च-आयामी सरणी भी सम्मिलित हैं (शिनहर 1974)। विभिन्न प्रारंभिक स्थितियों वाली समस्या के विभिन्न प्रकारों पर भी विचार किया गया है (कोबायाशी & गोल्डस्टीन 2005)।
फायरिंग स्क्वाड समस्या के समाधान को अन्य समस्याओं के लिए भी अपनाया जा सकता है। उदाहरण के लिए, पैट्रिक फिशर (1965) ने फायरिंग स्क्वाड सिंक्रोनाइज़ेशन समस्या के प्रथम समाधान के आधार पर अभाज्य संख्याएँ उत्पन्न करने के लिए सेलुलर ऑटोमेटन एल्गोरिदम डिज़ाइन किया।
संदर्भ
- Balzer, Robert (1967), "An 8-state minimal time solution to the firing squad synchronization problem", Information and Control, 10 (1): 22–42, doi:10.1016/S0019-9958(67)90032-0.
- Fischer, Patrick C. (1965), "Generation of primes by a one-dimensional real-time iterative array", Journal of the ACM, 12 (3): 388–394, doi:10.1145/321281.321290.
- Goto, Eiichi (1962), A minimal time solution of the firing squad problem, Dittoed course notes for Applied Mathematics 298, Cambridge, MA: Harvard University, pp. 52–59. As cited by Waksman (1966).
- Kobayashi, Kojiro; Goldstein, Darin (2005), "On formulations of firing squad synchronization problems", Unconventional Computation (PDF), Lecture Notes in Computer Science, vol. 3699, Springer-Verlag, pp. 157–168, doi:10.1007/11560319_15.
- Mazoyer, Jacques (1987), "A six-state minimal time solution to the firing squad synchronization problem", Theoretical Computer Science, 50 (2): 183–238, doi:10.1016/0304-3975(87)90124-1.
- Moore, F. R.; Langdon, G. G. (1968), "A generalized firing squad problem", Information and Control, 12 (3): 212–220, doi:10.1016/S0019-9958(68)90309-4.
- Shinahr, Ilka (1974), "Two- and three-dimensional firing-squad synchronization problem", Information and Control, 24 (2): 163–180, doi:10.1016/S0019-9958(74)80055-0.
- Waksman, Abraham (1966), "An optimum solution to the firing squad synchronization problem", Information and Control, 9 (1): 66–78, doi:10.1016/S0019-9958(66)90110-0.
