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

در عمل، اغلب توابع مربوط به بهره و سود، با ماشین‌های همیشه متوقف محاسبه می‌شوند. می‌توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می‌کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده‌ای باعث نمی‌شود که ماشین در حلقه بی‌نهایت وارد شود. به عنوان یک مثال جزئی می‌توان ماشینی را نام برد که درخت تصمیم‌گیری محدودی را اجرا می‌کند. علی‌رغم تضمین توقف، نیازی نیست که ماشین حتماً فاقد قابلیت‌های حلقه باشد. اگر ما حلقه‌ها را برای رسیدن به اندازه‌ای متناهی و قابل پیش‌بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می‌توانیم توابع بازگشتی اولیه را بیان کنیم. برای نمونه‌ی چنین ماشینی، می‌توان زبان اسباب‌بازی PL-{GOTO} را که توسط Brainerd و Landweber در ۱۹۷۴ معرفی شد، در نظر گرفت.

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

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

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

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 با هر ورودی متوقف شود، تصمیم‌ناپذیر است. در حقیقت این مسئله در سطح Π_۰^۲ سلسله مراتب حسابی قرار دارد. از اینرو این مسئله بسیار مشکل‌تر از مسئله توقف است که می‌پرسد آیا ماشین با ورودی صفر متوقف می‌شود یا خیر. به‌طور مستقیم، این تفاوت در حل‌ناپذیری به این علت است که هر نمونه از مسئله ماشین کلی بیانگر نمونه‌های نامحدود زیادی از مسئله توقف می‌باشد.

• ماشین محاسبه تورینگ

• 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.