مهم‌ترین ماشینی که هرگز ساخته نشد

تورینگ با ماشین انتزاعی خود مدلی از محاسبات را برای پاسخ به مسئله تصمیم‌گیری ایجاد کرد که این سوال را طرح می‌کند که: با توجه به مجموعه‌ای از اصول ریاضی، آیا یک فرایند مکانیکی (مجموعه‌ای از دستورالعمل‌ها که امروزه آن را الگوریتم می‌خوانیم) وجود دارد که همیشه درستی یک گزاره خاص را تعیین کند؟

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

اگرچه ممکن است تجزیه‌و‌تحلیل برخی از موقعیت‌ها بیشتر از عمر ما طول بکشد (الگوریتم ممکن است همه موقعیت‌های ممکن را ایجاد کند و هریک از آن‌ها را با ورودی مقایسه کند)، چنین الگوریتمی در بازی شطرنج وجود دارد. درنتیجه، می‌گوییم شطرنج «تصمیم‌پذیر» است.

با‌این‌حال، در سال ۱۹۳۶، چرچ و تورینگ (با استفاده از روش‌های متفاوتی) به‌طور مستقل ثابت کردند که راه‌حل کلی برای حل تمام نمونه‌های ممکن مسئله تصمیم‌گیری وجود ندارد. برای مثال، برخی از بازی‌ها نظیر بازی زندگی که توسط جان هورتون کانوی طراحی شده است، تصمیم‌پذیر نیستند. هیچ الگوریتمی نمی‌تواند تعیین کند که آیا الگوی خاصی از الگوی اولیه ظاهر خواهد شد یا نه.

تورینگ نشان داد تابع در صورتی محاسبه‌پذیر است که الگوریتمی وجود داشته باشد که بتواند وظیفه موردنظر را اجرا کند. در همین حین، او نشان داد که الگوریتم فرایندی است که می‌تواند توسط ماشین تورینگ تعریف شود. از‌این‌رو، تابع قابل محاسبه تابعی است که برای محاسبه آن ماشین تورینگی وجود داشته باشد. این تعریف ممکن است مانند راهی پرپیچ‌و‌خم برای تعریف محاسبه‌پذیری به‌نظر برسد، اما بهترین تعریفی است که داریم. مایکل سیپسر، دانشمند علوم نظری کامپیوتر از موسسه فناوری ماساچوست می‌گوید: «راه دیگری برای تعریف آن ندارید. فکر می‌کنم عموما پذیرفته شده است که تز چرچ-تورینگ می‌گوید مفهوم غیررسمی الگوریتم با آنچه هر مدل محاسباتی معقول بتواند انجام دهد، مطابقت دارد. »

ریاضیدانان دیگر مدل‌های محاسباتی مختلفی ارائه کرده‌اند که در ظاهر کاملا متفاوت به‌نظر می‌رسند اما درواقع معادل هستند: آن‌ها می‌توانند هر محاسباتی را انجام دهند که ماشین‌های تورینگ می‌توانند انجام دهند و بالعکس.

تنها چند سال پس از اینکه کورت گودل ثابت کرد ریاضیات ناقص است، چرچ و تورینگ با این کار نشان دادند که برخی از مسائل در ریاضیات غیرقابل تصمیم‌گیری هستند و هیچ الگوریتمی هرچند پیچیده، نمی‌تواند به ما بگوید که پاسخ مثبت است یا منفی.

هر دو مورد برای هیلبرت که امیدوار بود ریاضیات پاسخ‌های بی‌عیب و مشخصی داشته باشد، ضربات مهلکی محسوب می‌شدند. اگر راه‌حل کلی برای مسئله تصمیم‌گیری وجود داشت، به این معنا بود که کل مسائل ریاضی را می‌شد به محاسبات مکانیکی ساده تقلیل داد.

جدا از پاسخ به این سؤالات اساسی، ماشین تورینگ همچنین مستقیما منجر به ساخت کامپیوترهای مدرن ازطریق نسخه‌ای به نام «ماشین تورینگ جهانی» شد.

ماشین تورینگ جهانی نوع خاصی از ماشین تورینگ است که می‌تواند براساس هر ورودی، هر ماشین تورینگ دیگری را شبیه‌سازی کند. این نسخه ماشین تورینگ می‌تواند توصیفات سایر ماشین‌های تورینگ (قوانین و نوارهای ورودی آن‌ها) را بخواند و رفتار آن‌ها را روی نوار ورودی خودش شبیه‌سازی کند و همان خروجی را تولید کند که ماشین شبیه‌سازی‌شده آن را تولید می‌کند؛ درست همان‌طور که کامپیوترهای امروزی می‌توانند هر برنامه‌ای را بخوانند و آن را اجرا کنند.

در سال ۱۹۴۵، جان فون نویمان نوعی معماری کامپیوتر به نام معماری فون نویمان را پیشنهاد کرد که مفهوم ماشین تورینگ جهانی را در ماشین واقعی پیاده کرد.

وقتی سانجیو آرورا، دانشمند علوم نظری کامپیوتر در دانشگاه پرینستون این مفهوم را آموزش می‌دهد، بر تصویر فلسفی گسترده‌تری تاکید می‌کند. او توضیح می‌دهد: «دو مفهوم از «جهانی» وجود دارد. یکی از مفاهیم جهانی این است که می‌تواند هر ماشین تورینگ دیگری را اجرا کند. اما مفهوم بزرگ‌تر «جهانی» این است که می‌تواند هر محاسباتی را که در ذهن دارید، اجرا کند.»

در دنیای فیزیک کلاسیک، هر فرایند فیزیکی را می‌توان با استفاده از الگوریتم‌ها مدل‌سازی یا شبیه‌سازی کرد که به‌نوبه‌ی‌خود می‌تواند توسط ماشین تورینگ شبیه‌سازی شود.

یکی دیگر از انواع قابل‌توجه و مفیدتر ماشین‌های تورینگ، «ماشین تورینگ احتمالی» است. برخلاف ماشین تورینگ معمولی که واکنش کاملا مشخصی دربرابر هر ورودی دارد، ماشین تورینگ احتمالی براساس احتمالات می‌تواند چندین واکنش داشته باشد. این بدان معنا است که ماشین می‌تواند برای یک ورودی در زمان‌های مختلف نتایج متفاوتی به دست آورد. جالب اینکه این نوع استراتژی احتمالی می‌تواند کارآمدتر از رویکرد کاملا قطعی برای برخی مسائل باشد.

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