موضوع مقاله: ماشین تورینگ کامل | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین تورینگ کامل | مقدمه: در نظریه محاسبات ماشین همیشه متوقف که به عنوان‌های ماشین تورینگ کامل یا تصمیم‌گیرنده (Decider) نیز شناخته می‌شود، ماشینی است که با هر ورودی متوقف می‌شود. | ## بخش 1: ماشین تورینگ کامل | به دلیل توقف مداوم، این ماشین قادر است تصمیم بگیرد که آیا رشته داده شده مربوط به زبان فرمال است یا خیر. آن دسته از زبان‌هایی که توسط این ماشین‌ها تصمیم‌پذیر هستند، مجموعهٔ زبان‌های بازگشتی می‌باشند. اما با توجه به مسئلهٔ توقف، تعیین کردن توقف یک ماشین تورینگ دلخواه به ازای همه‌ی داده‌های ممکن، خود یک مسئله تصمیم‌ناپذیر است. توابع محاسبه‌پذیر در عمل، اغلب توابع مربوط به بهره و سود، با ماشین‌های همیشه متوقف محاسبه می‌شوند. می‌توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می‌کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده‌ای باعث نمی‌شود که ماشین در حلقه بی‌نهایت وارد شود. به عنوان یک مثال جزئی می‌توان ماشینی را نام برد که درخت تصمیم‌گیری محدودی را اجرا می‌کند. اگر ما حلقه‌ها را برای رسیدن به اندازه‌ای متناهی و قابل پیش‌بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می‌توانیم توابع بازگشتی اولیه را بیان کنیم. به‌علاوه می‌توانیم زبان برنامه‌نویسی تعریف کنیم که نشان دهد حتی توابع پیچیده‌تر نیز همیشه می‌توانند متوقف شوند. برای مثال، توابع آکرمان که تابع بازگشتی اولیه نیستند، با این حال به وسیلهٔ سیستم جملات بازنویسی شده و با روند کاهشی آرگومان‌ها تابعی محاسبه‌پذیر می‌باشند. | ## بخش 2: ماشین تورینگ کامل | با وجود مثال‌های بالا از زبان‌های برنامه‌نویسی که پایان برنامه را تضمین می‌کند، هیچ زبان برنامه‌نویسی دیگری وجود ندارد که توابع بازگشتی را در بر بگیرد، برای مثال توابعی که با ماشین‌های تورینگ همیشه متوقف محاسبه می‌شوند. این بخاطر این واقعیت است که وجود چنین زبان‌های برنامه‌نویسی با نیمه تصمیم‌ناپذیر مسایل در تناقض است اگرچه ماشین‌های تورینگ با هر ورودی متوقف می‌شود. ارتباط با ماشین‌آلات تورینگ جزئی یک ماشین تورینگ عمومی می‌تواند توابع جزئی را محاسبه کند. دو سؤال در رابطه با تفاوت ماشین‌های تورینگ کلی و جزئی می‌توان پرسید: آیا توابع جزئی که با ماشین‌های تورینگ جزئی محاسبه می‌شوند را می‌توان تا تبدیل آن‌ها به توابع محاسبه‌پذیر کلی گسترش داد؟ آیا امکان تغییر تعریف ماشین‌های تورینگ وجود دارد تا دسته خاصی از ماشین‌های تورینگ کلی، همه محاسبات توابع کلی را انجام دهد؟ برهان‌های زیر نشان می‌دهد توابعی که با ماشین‌های همیشه متوقف محاسبه می‌شوند را نمی‌توان به همه توابع محاسبه‌پذیر جزئی تعمیم داد که از این می‌توان اینطور فهمید که جواب سؤال اول منفی می‌باشد. برهان: توابع محاسبه‌پذیر جزئی تورینگی وجود دارد که به توابع محاسبه‌پذیر کلی تورینگ بسط داده نمی‌شوند. به‌طور خاص، تابع جزئی f تعریف می‌شود و داریم f(m)=n اگر و تنها اگر ماشین تورینگی که با شاخصn، ضمن ورود داده صفر با خروجی m متوقف می‌شود، تعمیمی به تابع محاسبه‌پذیر کلی نداشته باشد. در حقیقت، اگر g تابع محاسبه‌پذیر کلی گسترش‌یافته f باشد، آن‌گاه g می‌تواند توسط بعضی از ماشین‌های تورینگ قابل محاسبه باشد. | ## بخش 3: ماشین تورینگ کامل | با استفاده از قضیه بازگشت کلیین، ماشین تورینگ M را بسازید که در آن ورودی صفر ماشینی با شاخص e را شبیه‌سازی می‌کند که بر روی شاخص n_M برای M اجرا می‌شود. (در نتیجه ماشین M می‌تواند شاخص خودش را تولید کند و این همان نقش قضیه بازگشت است) فرض کنید این شبیه‌سازی نهایتاً به یک جواب برگردد. سؤال دوم در اصل می‌پرسد که آیا مدل محاسبه‌پذیر منطقی دیگری وجود دارد که فقط توابع کلی و همه توابع محاسبه‌پذیر کلی را محاسبه کند. اگر چنین مدلی وجود داشت آن‌گاه هریک از محاسبه‌کننده‌های آن می‌توانست توسط ماشین تورینگ شبیه‌سازی شود. در نتیجه اگر چنین مدلی شامل دنباله از ماشین باشد، دنباله شمارش‌پذیر بازگشتی از ماشین تورینگ وجود دارد که توابع کلی را محاسبه می‌کند و بنابراین هر تابع محاسبه‌پذیر کلی توسط یکی از ماشین‌های T_i محاسبه می‌شود و این غیرممکن است چرا که ماشین T این‌طور ساخته می‌شود که ورودی i ماشین T به 1+T_i (i) برگردد که این ماشین نمی‌تواند معادل هیچ‌یک از ماشین‌های T موجود در لیست باشد. اگر در لیست با شاخص j موجود بود، آن‌گاه داریم: T_j 1+ T_j= که به عدد صحیحی بازنمی‌گردد. (اگر تابع کلی شمارش‌پذیر بازگشتی باشد، آن‌گاه تابع می‌تواند ساخته شود) بنابراین با یک تناقض روبرو هستیم و این نشان می‌دهد که پاسخ سؤال دوم نیز منفی است. مجموع شاخص‌های ماشین تورینگ کلی مسئله توقف اینکه ماشین تورینگ با شاخص e با هر ورودی متوقف شود، تصمیم‌ناپذیر است. از اینرو این مسئله بسیار مشکل‌تر از مسئله توقف است که می‌پرسد آیا ماشین با ورودی صفر متوقف می‌شود یا خیر. | ## جمع‌بندی | به‌طور مستقیم، این تفاوت در حل‌ناپذیری به این علت است که هر نمونه از مسئله ماشین کلی بیانگر نمونه‌های نامحدود زیادی از مسئله توقف می‌باشد.