برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: یک ماشین تورینگ استاندارد توسط یک ۹ تائی به صورت m = (q, \ sigma, \ gamma, dash, \ , \ delta, s, t, r) تعریف می‌شود که در آن: مجموعه متناهی حالات است. مجموعه متناهی الفبای ورودی است. مجموعه متناهی الفبای نوار است. نشانگر پایان از سمت چپ است. نمایشگر یک فاصله خالی روی نوار است. تابع انتقال است. حالت شروع است. حالت پذیرش است. حالت عدم پذیرش است اگر حالت ابتدایی باشد، با خواندن نماد، یک انتقال به صورت تعریف می‌شود که در آن به جای قرار می‌گیرد و حالت ماشین به منتقل می‌شود و کلاهک خواندن در جهت (چپ یا راست) برای خواندن ورودی بعدی حرکت می‌کند. در ۲ dfa، همیشه با برابر است. این مدل معادل با dfa است. اثبات آن شامل ساخت جدولی است که نتایج حاصل از پیمایش معکوس با شرایط خاص را برای هر وضعیت داده‌شده فهرست می‌کند. در آغاز محاسبه، پیمایش معکوس برابر با تلاش برای گذشتن از نشانگر پایان است. در هر حرکت به سمت راست، جدول می‌تواند با استفاده از مقادیر جدول قبلی و کاراکتری که در خانه قبلی بوده‌است، به‌روز شود. چون تعداد حالت‌هایی که کلاهک می‌بیند ثابت است و تعداد حالت‌های الفبای نوار نیز ثابت است، اندازه جدول نیز ثابت است و می‌تواند توسط یک dfa دیگر پردازش شود. این مدل نیازی به پیمایش معکوس ندارد و از این جهت یک dfa است. بسیاری از انواع این مدل معادل با یک dfa هستند. به خصوص در حالت‌های غیر قطعی (که در آن‌ها با یک ورودی انتقال به چندین حالت ممکن است) هم قابل تبدیل به dfa می‌باشند. حالت‌های دیگر این مدل، پیچیدگی‌های محاسباتی بیشتری دارند. با یک پشته نا متناهی، این مدل می‌تواند تمام زبان‌هایی را که، با ماشین تورینگ در مرتبه زمانی خطی پردازش می‌شوند، تجزیه کند. به عنوان یک حالت خاص، زبان {anbncn} می‌تواند، تحت‌الگوریتمی که ابتدا تشخیص دهد تعداد aها و bها برابر و سپس تعداد bها و cها برابر هستند، تجزیه شود. با بهره‌گیری از مزایای عدم قطعیت، ماشین می‌تواند هر زبان مستقل از متنی را تجزیه و تحلیل کند. با ۲ حافظه پشته‌ای نامتناهی، ماشین معادل با یک تورینگ ماشین است و می‌تواند هر زبان صوری بازگشتی را تجزیه و تحلیل کند. اگر ماشین مجاز به داشتن چندین کلاهک باشد، با توجه به مجاز بودن یا نبودن عدم قطعیت، می‌تواند هر زبانی درl یا nl را تجزیه کند دستگاه دو طرفه متناهی کوانتومی مفهوم ۲ dfas توسط …
برداشت:
ماشین‌های خواندنی تورینگ یا ماشین‌های تعیین‌پذیر حالات متناهی ۲مسیره (به انگلیسی : read-only turing machine یا two-way deterministic finite-state automaton) (مخفف انگلیسی : ۲dfa) رده‌ای از مدل‌های محاسبه پذیری هستند که مانند یک ماشین تورینگ استاندارد عمل می‌کنند و می‌توانند در هر ۲ جهت روی نوار حرکت کنند اما نمی‌توانند چیزی بنویسند . در حقیقت این ماشین‌ها از نظر قدرت محاسباتی معادل یک ماشین تعیین‌پذیر حالات متناهی هستند که فقط می‌توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند .