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

در نظریه محاسبات ماشین‌های همیشه متوقف که به عنوان‌های تصمیم گیرنده (decider) یا ماشین تورینگ کامل نیز شناخته می‌شوند، ماشینی است که با هر ورودی متوقف می‌شود. به دلیل توقف مداوم، این ماشین قادر است تصمیم بگیرد که آیا رشته داده شده مربوط به زبان فرمال است یا خیر. آن دسته از زبان‌هایی که توسط این ماشین‌ها تصمیم پذیر هستند، مجموعه زبان‌های بازگشتی می‌باشند. اگرچه با توجه به مسئله توقف تعیین اینکه ماشین تورینگ اختیاری به ازای جمیع داده‌ها متوقف شود، خود یک مسئله تصمیم ناپذیر است.
توابع محاسبه‌پذیر
در عمل، اغلب توابع مربوط به بهره و سود، با ماشین‌های همیشه متوقف محاسبه می‌شوند. می‌توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می‌کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده‌ای باعث نمی‌شود که ماشین در حلقه بینهایت وارد شود. به عنوان یک مثال جزیی می‌توان ماشینی را نام برد که درخت تصمیم گیری محدودی را اجرا می‌کند. علی‌رغم تضمین توقف، نیازی نیست که ماشین حتما فاقد قابلیت‌های حلقه باشد. اگر ما حلقه‌ها را برای رسیدن به اندازه‌ای متناهی و قابل پیش‌بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می‌توانیم توابع بازگشتی اولیه را بیان کنیم. مثالی از چنین ماشین‌هایی را ماشین‌های برنامه‌نویسی زبان اسباب‌بازی ارائه می‌دهند.
بعلاوه می‌توانیم زبان برنامه‌نویسی تعریف کنیم که نشان دهد حتی توابع پیچیده‌تر نیز همیشه می‌توانند متوقف شوند. برای مثال، توابع اکرمن که تابع بازگشتی اولیه نیستند، با این حال بوسیله سیستم جملات بازنویسی شده و با روند کاهشی آرگومان‌ها تابعی محاسبه‌پذیر می‌باشند.
با وجود مثال‌های بالا از زبان‌های برنامه نویسی که پایان برنامه را تضمین می‌کند، هیچ زبان برنامه‌نویسی دیگری وجود ندارد که توابع بازگشتی را در بر بگیرد، برای مثال توابعی که با ماشین‌های تورینگ همیشه متوقف محاسبه می‌شوند. این بخاطر این واقعیت است که وجود چنین زبان‌های برنامه نویسی با نیمه تصمیم‌ناپذیر مسایل در تناقض است اگرچه ماشین‌های تورینگ با هر ورودی متوقف می‌شود.
ارتباط با ماشین‌آلات تورینگ جزئی
یک ماشین تورینگ عمومی می‌تواند توابع جزئی را محاسبه کند. دو سوال در رابطه با تفاوت ماشین‌های تورینگ کلی و جزئی می‌توان پرسید:
آیا توابع جزئی که با ماشین‌های تورینگ جزئی محاسبه می‌شوند را می‌توان تا تبدیل آن‌ها به توابع محاسبه‌پذیر کلی گسترش داد؟
آیا امکان تغییر تعریف ماشین‌های تورینگ وجود دارد تا دسته خاصی از ماشین‌های تورینگ کلی، همه محاسبات توابع کلی را انجام دهد؟ آیا پیدا می‌شود؟
پاسخ هر دو این سوال‌ها «خیر» است.
برهان‌های زیر نشان می‌دهد توابعی که با ماشین‌های همیشه متوقف محاسبه می‌شوند را نمی‌توان به همه توابع محاسبه‌پذیر جزئی تعمیم داد که از این می‌توان اینطور فهمید که جواب سوال اول منفی می‌باشد. این واقعیت رابطه نزدیکی با الگوریتم حل‌ناپذیر مسئله توقف دارد.
برهان: توابع محاسبه‌پذیر جزئی تورینگی وجود دارد که به توابع محاسبه‌پذیر کلی تورینگ بسط داده نمی‌شوند. بطور خاص، تابع جزئی 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 با هر ورودی متوقف شود، تصمیم‌ناپذیر است. در حقیقت این مسئله در سطح _۰^۲ سلسله مراتب حسابی قرار دارد. از اینرو این مسئله بسیار مشکل‌تر از مسئله توقف است که می‌پرسد آیا ماشین با ورودی صفر متوقف می‌شود یا خیر. به‌طور مستقیم، این تفاوت در حل‌ناپذیری به این علت است که هر نمونه از مسئله ماشین کلی بیانگر نمونه‌های نامحدود زیادی از مسئله توقف می‌باشد.
ماشین محاسبه تورینگ