ماشین صف

ماشین صف (به انگلیسی: queue machine)یک ماشین حالت متناهی است که توانایی ذخیره و بازیابی اطلاعات را از یک صف با حافظه بی‌نهایت دارد. این یک مدل محاسباتی معادل ماشین تورینگ است و بنابراین می‌تواند همان کلاس زبان رسمی را پردازش کند.

تئوری

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

${\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 )}$.^[۱]

تکامل تورینگ

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

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

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

کاربرد

ماشین‌های صف می‌توانند مدل ساده ای را برای ایجاد معماری‌های کامپیوتری،^[۳][۴]زبان‌های برنامه‌نویسی یا الگوریتم ارائه دهند.^[۵][۶]

منابع

1. Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider (ed.). Automata and Computability (hardcover). Undergraduate Texts in Computer Science (1 ed.). New York: Springer-Verlag. pp. 368–370. ISBN 0-387-94907-0.
2. Rus, Teodor. "Variants of Turing Machines" (PDF). Lecture Notes Covering Theory of Computation. University of Iowa, Iowa City, IA, 52242-1419. Archived from the original (PDF) on 21 September 2008. Retrieved 2007-11-06.
3. Feller, M.; M.D. Ercegovac (1981). "Queue machines: An organization for parallel computation". Lecture Notes in Computer Science. 111: 37. doi:10.1007/BFb0105108. Retrieved 2007-11-06.^{[پیوند مرده]}
4. Schmit, Herman; Benjamin Levine; Benjamin Ylvisaker (2002). "Queue Machines: Hardware Compilation in Hardware". 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02): 152. doi:10.1109/FPGA.2002.1106670. Retrieved 2007-11-06.
5. Moore, Christopher (1999-09-20). "Queues, Stacks, and Transcendentality at the Transition to Chaos". Algorithms Project's Seminar. INRIA. Retrieved 2007-11-06.
6. von Thum, Manfred (2007). "A queue machine for evaluating expressions". LaTrobe University. Archived from the original on 7 August 2007. Retrieved 2007-11-06.