Queue automaton
کیو مشین، کیو آٹومیٹن، یا پل اپ آٹومیٹن (پی یو اے) ایک محدود ریاستی مشین ہے جو لامحدود میموری قطار سے ڈیٹا کو ذخیرہ کرنے اور بازیافت کرنے کی صلاحیت رکھتی ہے۔ یہ ٹورنگ مشین کے مساوی حساب کا ایک نمونہ ہے، اور اس لیے یہ رسمی زبانوں کی اسی کلاس پر کارروائی کر سکتا ہے۔ ایک قطار مشین کو چھ ٹپل کے طور پر بیان کیا جا سکتا ہے جہاں ریاستوں کا ایک محدود مجموعہ ہے ؛ ان پٹ حروف تہجی کا محدود مجموعہ ہے ؛ محدود قطار حروف تہجی ہے ؛ ابتدائی قطار کی علامت ہے ؛ ابتدائی حالت ہے ؛ منتقلی فنکشن ہے۔ مشین کی ترتیب اس کی حالت اور قطار کے مندرجات کا ایک ترتیب شدہ جوڑا ہے، جہاں کلین کی بندش کی نشاندہی ہوتی ہے۔ ان پٹ سٹرنگ پر ابتدائی ترتیب کی تعریف اس طرح کی جاتی ہے، اور ایک ترتیب سے دوسری ترتیب میں منتقلی کی تعریف اس طرح کی جاتی ہے: جہاں قطار حروف تہجی سے ایک علامت ہے، قطار کی علامتوں () کی ترتیب ہے، اور۔ سلسلے میں قطار کی "فرسٹ ان فرسٹ آؤٹ" خاصیت کو نوٹ کریں۔ مشین ایک سٹرنگ کو قبول کرتی ہے اگر ٹرانزیشن کی ایک محدود تعداد کے بعد ابتدائی ترتیب سٹرنگ کو ختم کرنے کے لیے تیار ہوتی ہے (نیل سٹرنگ تک پہنچتی ہے)، یا دوسری صورت میں کہا جاتا ہے، اگر ٹورنگ مکمل ہے تو ہم یہ ثابت کر سکتے ہیں کہ ایک قطار مشین ٹورنگ مشین کے برابر ہے یہ ظاہر کر کے کہ ایک قطار مشین ٹورنگ مشین کی تقلید کر سکتی ہے اور اس کے برعکس۔ ایک ٹورنگ مشین کو ایک قطار والی مشین کے ذریعے نقل کیا جا سکتا ہے جو ٹورنگ مشین کے مندرجات کی ایک کاپی ہر وقت اپنی قطار میں رکھتی ہے، جس میں دو خاص مارکر ہوتے ہیں: ایک ٹورنگ مشین کے سر کی پوزیشن کے لیے، اور ایک ٹیپ کے آخر کے لیے ؛ اس کی منتقلی پوری قطار میں دوڑ کر، اس کی ہر علامت کو پاپ کر کے اور پاپ شدہ علامت کو دوبارہ حاصل کر کے، یا سر کی پوزیشن کے قریب، ٹورنگ مشین کے منتقلی کے اثر کے مساوی ٹورنگ مشین کی نقل کرتی ہے۔ ایک قطار مشین کو ٹورنگ مشین کے ذریعے نقل کیا جا سکتا ہے، لیکن زیادہ آسانی سے ایک ملٹی ٹیپ ٹورنگ مشین کے ذریعے، جو کہ ایک عام سنگل ٹیپ مشین کے مساوی ہونے کے لیے جانا جاتا ہے۔ سیمولیٹنگ کیو مشین ایک ٹیپ پر ان پٹ پڑھتی ہے اور دوسرے پر قطار کو محفوظ کرتی ہے، جس میں ٹیپ کے آغاز اور اختتام کی علامتوں میں سادہ منتقلی کے ذریعے پش اور پاپ کی وضاحت کی جاتی ہے۔ اس کا ایک رسمی ثبوت اکثر نظریاتی کمپیوٹر سائنس کے کورسز میں ایک مشق ہے۔ ایپلی کیشنز قطار مشینیں ایک آسان ماڈل پیش کرتی ہیں جس پر کمپیوٹر آرکیٹیکچرز، پروگرامنگ زبانیں، یا الگورتھم کی بنیاد رکھی جاتی ہے۔ کمپیوٹیبلٹی ٹورنگ مشین کے مساوی تعیناتی محدود آٹومیٹن پش ڈاؤن آٹومیٹن ٹیگ سسٹم مینوفیکٹریا بھی دیکھیں، ایک براؤزر فلیش گیم جو قطار مشین ماڈل کا استعمال کرتے ہوئے کھلاڑی کو مختلف الگورتھم کے نفاذ کے ساتھ کام کرتا ہے۔ حوالہ جات آٹومیٹا (حساب) حساب کے نمونے