Queue automaton
क्यू मशीन, क्यू ऑटोमेटन, या पुलअप ऑटोमेटन (पी. यू. ए.) एक सीमित अवस्था मशीन है जिसमें अनंत-स्मृति कतार से डेटा को संग्रहीत करने और पुनः प्राप्त करने की क्षमता होती है। यह एक ट्यूरिंग मशीन के समतुल्य गणना का एक मॉडल है, और इसलिए यह औपचारिक भाषाओं के उसी वर्ग को संसाधित कर सकता है। एक कतार मशीन को छह-टुपल के रूप में परिभाषित किया जा सकता है जहां अवस्थाओं का एक सीमित समूह है; इनपुट वर्णमाला का सीमित समूह है; सीमित कतार वर्णमाला है; प्रारंभिक कतार प्रतीक है; प्रारंभिक अवस्था है; संक्रमण कार्य है। एक मशीन विन्यास इसकी स्थिति और कतार सामग्री की एक क्रमबद्ध जोड़ी है, जहां के क्लेन बंद को दर्शाता है। एक इनपुट स्ट्रिंग पर प्रारंभिक विन्यास को इस प्रकार परिभाषित किया गया है, और एक विन्यास से दूसरे में संक्रमण को इस प्रकार परिभाषित किया गया हैः जहाँ कतार वर्णमाला से एक प्रतीक है, कतार प्रतीकों () का एक अनुक्रम है, और। संबंध में कतार के "फर्स्ट-इन-फर्स्ट-आउट" गुण पर ध्यान दें। मशीन एक स्ट्रिंग को स्वीकार करती है यदि संक्रमणों की एक सीमित संख्या के बाद प्रारंभिक विन्यास स्ट्रिंग को समाप्त करने के लिए विकसित होता है (नल स्ट्रिंग तक पहुँचता है), या अन्यथा कहा जाता है, यदि ट्यूरिंग पूर्णता हम यह साबित कर सकते हैं कि एक कतार मशीन एक ट्यूरिंग मशीन के बराबर है यह दिखाकर कि एक कतार मशीन एक ट्यूरिंग मशीन का अनुकरण कर सकती है और इसके विपरीत। एक ट्यूरिंग मशीन को एक कतार मशीन द्वारा अनुकरण किया जा सकता है जो हर समय अपनी कतार में ट्यूरिंग मशीन की सामग्री की एक प्रति रखता है, दो विशेष मार्करों के साथः एक ट्यूरिंग मशीन के सिर की स्थिति के लिए, और एक टेप के अंत के लिए; इसके संक्रमण पूरी कतार में दौड़कर ट्यूरिंग मशीन का अनुकरण करते हैं, इसके प्रत्येक प्रतीक को पॉप करते हैं और या तो पॉप किए गए प्रतीक को फिर से जोड़ते हैं, या, सिर की स्थिति के पास, ट्यूरिंग मशीन संक्रमण के प्रभाव के बराबर। एक कतार मशीन को एक ट्यूरिंग मशीन द्वारा अनुकरण किया जा सकता है, लेकिन एक बहु-टेप ट्यूरिंग मशीन द्वारा अधिक आसानी से, जिसे एक सामान्य एकल-टेप मशीन के बराबर माना जाता है। सिम्युलेटिंग कतार मशीन एक टेप पर इनपुट पढ़ती है और दूसरे पर कतार को संग्रहीत करती है, जिसमें टेप के शुरुआती और अंतिम प्रतीकों में सरल संक्रमण द्वारा परिभाषित धक्का और पॉप होते हैं। इसका एक औपचारिक प्रमाण अक्सर सैद्धांतिक कंप्यूटर विज्ञान पाठ्यक्रमों में एक अभ्यास है। अनुप्रयोग कतार मशीनें एक सरल मॉडल प्रदान करती हैं जिस पर कंप्यूटर वास्तुकला, प्रोग्रामिंग भाषाओं या एल्गोरिदम को आधार बनाया जाता है। कम्प्यूटेबिलिटी ट्यूरिंग मशीन समकक्ष निर्धारित सीमित स्वचालित पुशडाउन स्वचालित टैग सिस्टम मैन्युफैक्टोरिया, एक ब्राउज़र फ्लैश गेम है जो एक कतार मशीन मॉडल का उपयोग करके विभिन्न एल्गोरिदम के कार्यान्वयन के साथ खिलाड़ी को कार्य करता है। संदर्भ स्वचालित (गणना) गणना के मॉडल