ماشین صف

یک ماشین صف با شش تایی زیر تعریف می‌شود:

${\displaystyle M=(Q,\Sigma ,\Gamma ,\$,s,\delta )}$

• ${\displaystyle \,Q}$ مجوعه حالات متناهی
• ${\displaystyle \,\Sigma \subset \Gamma }$ مجموعه متناهی الفبای ورودی
• ${\displaystyle \,\Gamma }$ صف محدود الفبا
• ${\displaystyle \,\$\in \Gamma -\Sigma }$ نماد اولیه صف است.
• ${\displaystyle \,s\in Q}$ حالت شروع
• ${\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}$ تابع انتقال

یک پیکر بندی ماشین، به صورت دوتایی حالت و محتوای صف است و به صورت ${\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}$ نشان داده می‌شود، که${\displaystyle \,\Gamma ^{*}}$ به معنای ستاره کلین ${\displaystyle \,\Gamma }$ می‌باشد. پیکربندی شروع با رشته ورودی${\displaystyle \,x}$ به صورت ${\displaystyle \,(s,x\$)}$ تعریف می‌شود و انتقال ${\displaystyle \rightarrow _{M}^{1}}$ از یک پیکربندی به پیکربندی بعدی به صورت زیر بیان می‌شود:

${\displaystyle \,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )}$

که ${\displaystyle A}$ نشانه ای از صف الفبا،${\displaystyle \alpha }$ یک دنباله از نمادهای صف(${\displaystyle \alpha \in \Gamma ^{*}}$)، و ${\displaystyle (q,\gamma )=\delta (p,A)}$. توجه داشته باشید که ویژگی "first-in-first-out" از صف در رابطه وجود دارد.

ماشین رشته ${\displaystyle \,x\in \Sigma ^{*}}$ را قبول می‌کند اگر پس از یک تعداد محدودی از انتقال، پیکربندی شروع آنقدر پیش برود تا رشته را تهی کند (به رشته صفر برسد${\displaystyle \,\epsilon }$) یا${\displaystyle \,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon )}$.[1]

ما می‌توانیم ثابت کنیم که یک ماشین صف معادل یک ماشین تورینگ است. با نشان دادن اینکه ماشین صف می‌تواند دستگاه تورینگ را شبیه‌سازی کند و برعکس این امر اثبات می‌شود.

ماشین تورینگ را می‌توان با یک ماشین صف شبیه‌سازی کرد که محتویات ماشین تورینگ را در صف خود در همه زمان‌ها نگهداری می‌کند و دو نشانگر مخصوص در نظر گرفته می‌شود: یکی برای موقعیت آغاز TM و یکی برای پایان.انتقالات آن، از طریق آن دسته از TM که در سراسر صف اجرا می‌شود شبیه‌سازی می‌شود.

یک ماشین صف می‌تواند توسط یک ماشین تورینگ شبیه‌سازی شود، اما این شبیه‌سازی توسط ماشین تورینگ چندنواره بسیار راحت‌تر است. ماشین صف شبیه‌سازی شده ورودی را از یک نوار می‌خواند و در دومی ذخیره می‌کند و push و pop از صف با یک انتقال ساده به موقعیت آغاز و پایان نوار تعریف می‌شود.[2]

ماشین‌های صف می‌توانند مدل ساده ای را برای ایجاد معماری‌های کامپیوتری،[3][4]زبان‌های برنامه‌نویسی یا الگوریتم ارائه دهند.[5][6]