ماشین خواندنی تورینگ

ماشین‌های خواندنی تورینگ یا ماشین‌های تعیین‌پذیر حالات متناهی ۲مسیره (به انگلیسی: Read-only Turing machine یا Two-way deterministic finite-state automaton) (مخفف انگلیسی: 2DFA) رده‌ای از مدل‌های محاسبه پذیری هستند که مانند یک ماشین تورینگ استاندارد عمل می‌کنند و می‌توانند در هر ۲ جهت روی نوار حرکت کنند اما نمی‌توانند چیزی بنویسند.

در حقیقت این ماشین‌ها از نظر قدرت محاسباتی معادل یک ماشین تعیین‌پذیر حالات متناهی هستند که فقط می‌توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند.

نظریه

یک ماشین تورینگ استاندارد توسط یک ۹ تائی به صورت M = (Q, \Sigma, \Gamma, \vdash, \_, \delta, s, t, r) تعریف می‌شود که در آن:

• ${\displaystyle Q}$مجموعهٔ متناهی حالات است.
• ${\displaystyle \Sigma }$ مجموعهٔ متناهی الفبای ورودی است.
• ${\displaystyle \Gamma }$ مجموعهٔ متناهی الفبای نوار است.
• ${\displaystyle \vdash \in \Gamma -\Sigma }$ نشانگر پایان از سمت چپ است.
• ${\displaystyle \_\in \Gamma -\Sigma }$نمایشگر یک فاصلهٔ خالی روی نوار است.
• ${\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}}$ تابع انتقال است.
• ${\displaystyle s\in Q}$ حالت شروع است.
• ${\displaystyle t\in Q}$ حالت پذیرش است.
• ${\displaystyle r\in Q,~r\neq t}$ حالت عدم پذیرش است

اگر حالت ابتدایی ${\displaystyle q}$ باشد، با خواندن نماد ${\displaystyle a}$، یک انتقال به صورت ${\displaystyle \delta (q,a)=(q_{2},a_{2},d)}$ تعریف می‌شود که در آن ${\displaystyle a_{2}}$ به جای ${\displaystyle a}$ قرار می‌گیرد و حالت ماشین به ${\displaystyle q_{2}}$ منتقل می‌شود و کلاهک خواندن در جهت ${\displaystyle d}$ (چپ یا راست) برای خواندن ورودی بعدی حرکت می‌کند.^[۱] در2DFA، ${\displaystyle a_{2}}$ همیشه با ${\displaystyle a}$ برابر است.
این مدل معادل با DFA است. اثبات آن شامل ساخت جدولی است که نتایج حاصل از پیمایش معکوس با شرایط خاص را برای هر وضعیت داده شده فهرست می‌کند. در آغاز محاسبه، پیمایش معکوس برابر با تلاش برای گذشتن از نشانگر پایان است.

در هر حرکت به سمت راست، جدول می‌تواند با استفاده از مقادیر جدول قبلی و کاراکتری که در خانهٔ قبلی بوده‌است، به روز شود. چون تعداد حالت‌هایی که کلاهک می‌بیند ثابت است و تعداد حالت‌های الفبای نوار نیز ثابت است، اندازه جدول نیز ثابت است و می‌تواند توسط یک DFA دیگر پردازش شود. این مدل نیازی به پیمایش معکوس ندارد و از این جهت یک DFA است.

انواع

بسیاری از انواع این مدل معادل با یک DFA هستند. به خصوص در حالت‌های غیر قطعی (که در آن‌ها با یک ورودی انتقال به چندین حالت ممکن است) هم قابل تبدیل به DFA می‌باشند.

حالت‌های دیگر این مدل، پیچیدگی‌های محاسباتی بیشتری دارند. با یک پشتهٔ نا متناهی، این مدل می‌تواند تمام زبان‌هایی را که، با ماشین تورینگ در مرتبهٔ زمانی خطی پردازش می‌شوند، تجزیه کند.^[۲] به عنوان یک حالت خاص، زبان {aⁿbⁿcⁿ} می‌تواند، تحت‌الگوریتمی که ابتدا تشخیص دهد تعداد aها و bها برابر و سپس تعداد bها و cها برابر هستند، تجزیه شود.

با بهره‌گیری از مزایای عدم قطعیت، ماشین می‌تواند هر زبان مستقل از متنی را تجزیه و تحلیل کند.

با ۲ حافظهٔ پشته‌ای نامتناهی، ماشین معادل با یک تورینگ ماشین است و می‌تواند هر زبان صوری بازگشتی را تجزیه و تحلیل کند.
اگر ماشین مجاز به داشتن چندین کلاهک باشد، با توجه به مجاز بودن یا نبودن عدم قطعیت، می‌تواند هر زبانی درL یا NL را تجزیه کند دستگاه دو طرفه متناهی کوانتومی مفهوم 2DFAs توسط رابین و اسکات در سال 1959در کار اصلی خود که "ماشین های متناهی و مشکلات تصمیم گیری" نام داشت مطرح شد که در سال 1997 توسطJohn Watrous به محاسبات کوانتومی تعمیم یاقته بود "On the Power of 2-Way Quantum Finite State Automata" ، که او در آن نشان می‌دهد که این دستگاه می‌تواند زبان نامنظم تشخیص دهد و بسیار قوی تر از DFAها می‌باشد .

دستگاه دو طرفه پشته ای

یک دستگاه پشته ای است که اجازه حرکت در هر مسیری بر روی نوار ورودی خود را دارد که به آن  دستگاه دو طرفه پشته ای  (2PDA) میگویند که توسط Hartmanis، لوئیس، و استرنز در سال 1965  مطالعه شده‌است. Aho، Hopcroft، اولمن در سال 1968 و کوک در سال 1971کلاس زبان‌های تشخیص دهنده  2DPDA (قطعی) و غیر قطعی (2NPDA) دستگاه دو طرفه پشته ای را مشخص کردند. گری، هریسون، و ایبارا (1967) خواص بستار این زبان‌ها را بررسی کرده‌اند.

.^[۳]

کاربردها

ماشین خواندنی تورینگ در تعریف ماشین محاسبه تورینگ برای پذیرش ماشین تورینگی که می‌خواهد مدل سازی شود، استفاده می‌شود. پس از آن، محاسبات با یک ماشین تورینگ استاندارد ادامه می‌یابد.

در پژوهش‌های مدرن، این مدل برای توصیف رده جدیدی از Quantum finite automata یا probabilistic automata اهمیت پیدا کرده‌است.

جستارهای وابسته

ماشین پشته‌ای

منابع

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. 158, 210, 224. ISBN 0-387-94907-0.
2. Computational Complexity by Wagner and Wechsung, section 13.3 (1986, ISBN 90-277-2146-7)
3. Computational Complexity by Wagner and Wechsung, section 13.1 (1986, ISBN 90-277-2146-7)