ماشین تورینگ کامل

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه محاسبات ماشین‌های همیشه متوقف (به انگلیسی: total Turing machine) که به عنوان‌های تصمیم گیرنده (decider) یا ماشین تورینگ کامل (به انگلیسی: total Turing machine) نیز شناخته می‌شوند، ماشینی است که با هر ورودی متوقف می‌شود. به دلیل توقف مداوم، این ماشین قادر است تصمیم بگیرد که آیا رشته داده شده مربوط به زبان فرمال است یا خیر. آن دسته از زبان‌هایی که توسط این ماشین‌ها تصمیم پذیر هستند، مجموعه زبان‌های بازگشتی می‌باشند. اگرچه با توجه به مسئله توقف تعیین اینکه ماشین تورینگ اختیاری به ازای جمیع داده‌ها متوقف شود، خود یک مسئله تصمیم ناپذیر است.

توابع محاسبه‌پذیر[ویرایش]

در عمل، اغلب توابع مربوط به بهره و سود، با ماشین‌های همیشه متوقف محاسبه می‌شوند. می‌توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می‌کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده‌ای باعث نمی‌شود که ماشین در حلقه بینهایت وارد شود. بعنوان یک مثال جزیی می‌توان ماشینی را نام برد که درخت تصمیم گیری محدودی را اجرا می‌کند. علی‌رغم تضمین توقف، نیازی نیست که ماشین حتماً فاقد قابلیت‌های حلقه باشد. اگر ما حلقه‌ها را برای رسیدن به اندازه‌ای متناهی و قابل پیش‌بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می‌توانیم توابع بازگشتی اولیه را بیان کنیم. مثالی از چنین ماشین‌هایی را ماشین‌های برنامه‌نویسی زبان اسباب‌بازی ارائه می‌دهند.

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

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

ارتباط با ماشین‌آلات تورینگ جزئی[ویرایش]

یک ماشین تورینگ عمومی می‌تواند توابع جزئی را محاسبه کند. دو سؤال در رابطه با تفاوت ماشین‌های تورینگ کلی و جزئی می‌توان پرسید:

  1. آیا توابع جزئی که با ماشین‌های تورینگ جزئی محاسبه می‌شوند را می‌توان تا تبدیل آن‌ها به توابع محاسبه‌پذیر کلی گسترش داد؟
  2. آیا امکان تغییر تعریف ماشین‌های تورینگ وجود دارد تا دسته خاصی از ماشین‌های تورینگ کلی، همه محاسبات توابع کلی را انجام دهد؟ آیا پیدا می‌شود؟

پاسخ هر دو این سؤال‌ها «خیر» است.

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

  • برهان: توابع محاسبه‌پذیر جزئی تورینگی وجود دارد که به توابع محاسبه‌پذیر کلی تورینگ بسط داده نمی‌شوند. بطور خاص، تابع جزئی f تعریف می‌شود و داریم f(m)=n اگر و تنها اگر ماشین تورینگی که با شاخصn، ضمن ورود داده صفر با خروجی m متوقف می‌شود، تعمیمی به تابع محاسبه‌پذیر کلی نداشته باشد.

در حقیقت، اگر g تابع محاسبه‌پذیر کلی گسترش‌یافته f باشد، آن‌گاه g می‌تواند توسط بعضی از ماشین‌های تورینگ قابل محاسبه باشد. e را شاخص چنین ماشین‌هایی قرار دهید. با استفاده از قضیه بازگشت کلیین، ماشین تورینگ M را بسازید که در آن ورودی صفر ماشینی با شاخص e را شبیه‌سازی می‌کند که بر روی شاخص n_M برای M اجرا می‌شود. (درنتیجه ماشین M می‌تواند شاخص خودش را تولید کند و این همان نقش قضیه بازگشت است) فرض کنید این شبیه‌سازی نهایتاً به یک جواب برگردد. M را تعریف کنید، سپس اگر g(nM) = m آنگاه مقدار بازگشتی M، m+1 می‌شود؛ بنابراین f(nM)، مقدار بازگشتی درستM روی ورودی صفر، با g(nM) برابر نمی‌شود. در نتیجه g، f را گسترش نمی‌دهد.

سؤال دوم در اصل می‌پرسد که آیا مدل محاسبه‌پذیر منطقی دیگری وجود دارد که فقط توابع کلی و همه توابع محاسبه‌پذیر کلی را محاسبه کند. اگر چنین مدلی وجود داشت آن‌گاه هریک از محاسبه کننده‌های آن می‌توانست توسط ماشین تورینگ شبیه‌سازی شود. درنتیجه اگر چنین مدلی شامل دنباله از ماشین باشد، دنباله شمارش‌پذیر بازگشتی از ماشین تورینگ وجود دارد که توابع کلی را محاسبه می‌کند و بنابراین هر تابع محاسبه‌پذیر کلی توسط یکی از ماشین‌های T_i محاسبه می‌شود و این غیر ممکن است چرا که ماشین Tاین‌طور ساخته می‌شود که ورودی i ماشین T به 1+T_i (i) برگردد که این ماشین نمی‌تواند معادل هیچ‌یک از ماشین‌های T موجود در لیست باشد. اگر در لیست با شاخص j موجود بود، آن‌گاه داریم: T_j 1+ T_j= که به عدد صحیحی بازنمی‌گردد. پس نمی‌تواند کلی باشد درصورتی‌که تابعی که ساخته می‌شود باید کلی باشد. (اگر تابع کلی شمارش‌پذیر بازگشتی باشد، آن‌گاه تابع می‌تواند ساخته شود) بنابراین با یک تناقض روبرو هستیم و این نشان می‌دهد که پاسخ سؤال دوم نیز منفی است.

مجموع شاخص‌های ماشین تورینگ کلی[ویرایش]

مسئله توقف اینکه ماشین تورینگ با شاخص e با هر ورودی متوقف شود، تصمیم‌ناپذیر است. در حقیقت این مسئله در سطح Π_۰^۲ سلسله مراتب حسابی قرار دارد. از اینرو این مسئله بسیار مشکل‌تر از مسئله توقف است که می‌پرسد آیا ماشین با ورودی صفر متوقف می‌شود یا خیر. به‌طور مستقیم، این تفاوت در حل‌ناپذیری به این علت است که هر نمونه از مسئله ماشین کلی بیانگر نمونه‌های نامحدود زیادی از مسئله توقف می‌باشد.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Machine that always halts»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۷ ژانویه ۲۰۱۵).
  • Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
  • Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.
  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Kozen, D.C. (1997), Automata and Computability, Springer.
  • Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.