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