اگرچه ممکن است تجزیه و تحلیل برخی موقعیت ها بیشتر از عمر ما را ببرد (الگوریتم می تواند تمام موقعیت های ممکن را ایجاد کند و هر یک از آنها را با ورودی مقایسه کند)، چنین الگوریتمی در بازی شطرنج وجود دارد. بنابراین می گوییم شطرنج «تصمیم پذیر» است.
تورینگ نشان داد که یک تابع در صورتی قابل محاسبه است که الگوریتمی وجود داشته باشد که بتواند وظیفه مورد نظر را انجام دهد. در همان زمان، او نشان داد که الگوریتم فرآیندی است که می تواند توسط ماشین تورینگ تعریف شود. بنابراین، تابع قابل محاسبه تابعی است که برای آن ماشین تورینگ وجود دارد. این تعریف ممکن است روشی پیچیده برای تعریف محاسبه پذیری به نظر برسد، اما بهترین تعریفی است که ما داریم. مایکل سیپسر، دانشمند نظری کامپیوتر در موسسه فناوری ماساچوست، می گوید: «راه دیگری برای تعریف آن وجود ندارد. من فکر می‌کنم به طور کلی پذیرفته شده است که تز چرچ-تورینگ می‌گوید که مفهوم غیررسمی یک الگوریتم کاری است که هر مدل محاسباتی معقولی می‌تواند انجام دهد. »
در دنیای فیزیک کلاسیک، هر فرآیند فیزیکی را می‌توان با استفاده از الگوریتم‌ها مدل‌سازی یا شبیه‌سازی کرد که به نوبه خود توسط ماشین تورینگ شبیه‌سازی می‌شود.
دیگر ریاضیدانان مدل‌های محاسباتی مختلفی ارائه کرده‌اند که در ظاهر کاملاً متفاوت به نظر می‌رسند، اما در واقع معادل هستند: آنها می‌توانند هر محاسباتی را که ماشین‌های تورینگ می‌توانند انجام دهند، انجام دهند و بالعکس.
تورینگ با ماشین انتزاعی خود یک مدل محاسباتی برای پاسخ به مسئله تصمیم ایجاد کرد که این سوال را مطرح می کند: با توجه به مجموعه ای از اصول ریاضی، آیا یک فرآیند مکانیکی (مجموعه ای از دستورالعمل ها که اکنون آن را الگوریتم می نامیم) وجود دارد که همیشه حقیقت را تعیین می کند. یک پیشنهاد خاص؟
علاوه بر پاسخ به این سؤالات اساسی، ماشین تورینگ به لطف نسخه ای به نام «ماشین تورینگ جهانی» مستقیماً به ساخت رایانه های مدرن نیز منجر شد.
فرض کنید می‌خواهیم الگوریتمی پیدا کنیم که به ما بگوید آیا یک موقعیت خاص شطرنج امکان‌پذیر است یا خیر. در اینجا قوانین شطرنج بر حرکات مجاز حاکم است. آیا می توانیم برای رسیدن به موقعیت مورد نظر، دنباله ای محدود از روش های گام به گام را دنبال کنیم؟
وقتی سانجیو آرورا، دانشمند نظری کامپیوتر در دانشگاه پرینستون، این مفهوم را آموزش می‌دهد، بر دیدگاه فلسفی گسترده‌تری تأکید می‌کند. او توضیح می‌دهد که «جهانی» دو معنی دارد. یکی از مفاهیم جهانی این است که می تواند هر ماشین تورینگ دیگری را پیاده سازی کند. “اما معنای گسترده تر “جهانی” این است که می تواند هر محاسبه ای را که فکرش را بکنید انجام دهد.”
ایده ماشین های تورینگ ممکن در مناطقی مانند رمزگذاری، بهینه سازی و یادگیری ماشینی مفید شده است. این ماشین‌های انتزاعی شاید بهترین گواه باشند که پرسیدن سؤالات اساسی می‌تواند یکی از مفیدترین کارهایی باشد که یک دانشمند می‌تواند انجام دهد.
هر دو مورد ضربات مهلکی برای هیلبرت در نظر گرفته شد که امیدوار بود ریاضیات پاسخ های روشن و بی عیب و نقصی داشته باشد. اگر یک راه حل کلی برای مسئله تصمیم وجود داشت، به این معنی بود که کل مسائل ریاضی را می توان به محاسبات مکانیکی ساده تقلیل داد.
تنها چند سال پس از اینکه کرت گودل ثابت کرد که ریاضیات ناقص است، چرچ و تورینگ نشان دادند که برخی از مسائل در ریاضیات غیرقابل تصمیم گیری هستند و هیچ الگوریتمی، مهم نیست که چقدر پیچیده است، نمی تواند به ما بگوید که آیا پاسخ مثبت است یا خیر.
با این حال، در سال 1936، چرچ و تورینگ به طور مستقل (با استفاده از روش‌های مختلف) ثابت کردند که هیچ راه‌حل کلی برای همه موارد ممکن مشکل تصمیم وجود ندارد. به عنوان مثال، برخی از بازی ها مانند بازی زندگی جان هورتون کانوی قابل تصمیم گیری نیستند. هیچ الگوریتمی نمی تواند تعیین کند که آیا یک الگوی خاص از الگوی اولیه ظاهر می شود یا خیر.
در سال 1945، جان فون نویمان نوعی معماری کامپیوتری به نام معماری فون نویمان را پیشنهاد کرد که مفهوم ماشین تورینگ جهانی را در یک ماشین واقعی پیاده سازی کرد.
ماشین تورینگ جهانی نوع خاصی از ماشین تورینگ است که می تواند هر ماشین تورینگ دیگری را بر اساس هر ورودی شبیه سازی کند. این نسخه از ماشین تورینگ می تواند توضیحات سایر ماشین های تورینگ (قوانین و باندهای ورودی آنها) را بخواند و رفتار آنها را در باند ورودی خودش شبیه سازی کند و همان خروجی را تولید کند که ماشین شبیه سازی شده تولید می کند. درست مانند کامپیوترهای امروزی که می توانند هر برنامه ای را بخوانند و اجرا کنند.
یکی دیگر از انواع قابل توجه و مفیدتر ماشین تورینگ، “ماشین تورینگ احتمالی” است. بر خلاف ماشین تورینگ معمولی که واکنش خاصی به هر ورودی دارد، ماشین تورینگ احتمالی می تواند بر اساس احتمالات واکنش های متعددی داشته باشد. این بدان معناست که دستگاه ممکن است نتایج متفاوتی را برای یک ورودی مشابه در زمان‌های مختلف تولید کند. جالب توجه است که این نوع استراتژی احتمالی می تواند موثرتر از یک رویکرد کاملا قطعی برای برخی مشکلات باشد.
تحریریه مجله بازی یک گیمر