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

ماشین‌های خواندنی تورینگ یا ماشین‌های تعیین‌پذیر حالات متناهی ۲مسیره رده‌ای از مدل‌های محاسبه پذیری هستند که مانند یک ماشین تورینگ استاندارد عمل می‌کنند و می‌توانند در هر ۲ جهت روی نوار حرکت کنند اما نمی‌توانند چیزی بنویسند.
در حقیقت این ماشین‌ها از نظر قدرت محاسباتی معادل یک ماشین تعیین‌پذیر حالات متناهی هستند که فقط می‌توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند.
نظریه
یک ماشین تورینگ استاندارد توسط یک ۹ تائی به صورت M = (Q, \Sigma, \Gamma, \vdash, \_, \delta, s, t, r) تعریف می‌شود که در آن:
مجموعه متناهی حالات است.
مجموعه متناهی الفبای ورودی است.
مجموعه متناهی الفبای نوار است.
نشانگر پایان از سمت چپ است.
نمایشگر یک فاصله خالی روی نوار است.
تابع انتقال است.
حالت شروع است.
حالت پذیرش است.
حالت عدم پذیرش است
اگر حالت ابتدایی باشد، با خواندن نماد ، یک انتقال به صورت تعریف می‌شود که در آن به جای قرار می‌گیرد و حالت ماشین به منتقل می‌شود و کلاهک خواندن در جهت (چپ یا راست) برای خواندن ورودی بعدی حرکت می‌کند. در 2DFA ، همیشه با برابر است.
این مدل معادل با DFA است. اثبات آن شامل ساخت جدولی است که نتایج حاصل از پیمایش معکوس با شرایط خاص را برای هر وضعیت داده شده فهرست می‌کند. در آغاز محاسبه، پیمایش معکوس برابر با تلاش برای گذشتن از نشانگر پایان است.
در هر حرکت به سمت راست، جدول می‌تواند با استفاده از مقادیر جدول قبلی و کاراکتری که در خانه قبلی بوده است، به روز شود. چون تعداد حالت‌هایی که کلاهک می‌بیند ثابت است و تعداد حالت‌های الفبای نوار نیز ثابت است، اندازه جدول نیز ثابت است و می‌تواند توسط یک DFA دیگر پردازش شود. این مدل نیازی به پیمایش معکوس ندارد و از این جهت یک DFA است.
انواع
بسیاری از انواع این مدل معادل با یک DFA هستند. به خصوص در حالت‌های غیر قطعی (که در آنها با یک ورودی انتقال به چندین حالت ممکن است) هم قابل تبدیل به DFA می‌باشند.
حالت‌های دیگر این مدل، پیچیدگی‌های محاسباتی بیشتری دارند. با یک پشته نا متناهی، این مدل می‌تواند تمام زبان‌هایی را که، با ماشین تورینگ در مرتبه زمانی خطی پردازش می‌شوند، تجزیه کند. به عنوان یک حالت خاص، زبان {a n b n c n می‌تواند، تحت‌الگوریتمی که ابتدا تشخیص دهد تعداد 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 اهمیت پیدا کرده است.
ماشین پشته‌ای