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