محاسبات مفهومی آشنا است که بیشتر ما به‌طور شهودی آن را درک می‌کنیم. تابع (f(x) = x + 3) را درنظر بگیرید که در آن وقتی مقدار x برابر سه باشد (f(3) = 3 + 3)، جواب تابع شش می‌شود.

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

در سال ۱۹۲۸، دیوید هیلبرت و ویلهلم آکرمان، ریاضیدانان آلمانی مسئله‌ای به نام ﻣﺴﺌﻠﻪ ﺗﺼﻤﯿﻢ‌ﮔﯿﺮی (Entscheidungsproblem) را مطرح کردند. با گذشت زمان، مسئله آن‌ها به تعریف رسمی محاسبه‌پذیری متنهی شد و به ریاضیدانان اجازه داد به انبوهی از مسائل جدید پاسخ دهند و اساس علوم نظری کامپیوتر را ایجاد کرد.

به‌نقل از ﮐﻮاﻧﺘﺎ ﻣﮕﺰﯾﻦ تعریف مذکور حاصل اندیشه دانشجوی ۲۳ ساله‌ای به نام آلن تورینگ بود که در سال ۱۹۳۶ مقاله بنیادینی را نوشت که نه‌تنها به مفهوم محاسبات رسمیت بخشید، بلکه پرسشی اساسی را در ریاضیات ثابت کرد و پایه فکری اختراع کامپیوتر الکترونیکی را بنا نهاد.

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

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

ماشین تورینگ می‌تواند طبق جدولی از قوانین، نمادهای روی یک نوارِ بی‌نهایت طولانی را بخواند و تغییر دهد. نوار از خانه‌هایی تشکیل شده است که هریک می‌توانند یک نماد را ذخیره کنند و ماشین محتوای هر خانه را با هد نوار می‌خواند و بازنویسی می‌کند.

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

بهترین راه برای درک ماشین تورینگ، درنظر گرفتن مثالی ساده است. ماشینی را تصور کنید که طراحی شده است تا به ما بگوید که آیا یک ورودی خاص عدد صفر است یا نه.

برای نشان دادن این موضوع، از عدد ورودی ۰۰۰۱ به همراه نماد (#) استفاده می‌کنیم (#0001#)، بنابراین #0001# قسمت موردنظر روی نوار ما است.

ماشین در حالت اولیه شروع می‌کند که آن را q0 می‌نامیم. ماشین از خانه‌های سمت چپ روی نوار شروع می‌کند و به نماد # می‌رسد (که اعداد درون آن قرار دارند). قوانین چنین می‌گویند که وقتی درحالت q0 قرار دارید، اگر نماد # باشد، کاری به آن نداشته باشید، یک سلول به سمت راست بروید و حالت ماشین را به q1 تغییر دهید. پس از این مرحله، ماشین در حالت q1 قرار دارد و هد آن درحال خواندن نماد دوم یعنی 0 است.

اکنون به دنبال قاعده‌ای هستیم که روی این شرایط اعمال شود و قاعده‌ای را پیدا می‌کنیم که می‌گوید: در حالت q1 بمان و هد را روی سلول سمت راست ببر. این امر موجب می‌شود در همان موقعیت بمانیم (در حالت q1، خواندن 0). بنابراین، ما به حرکت به سمت راست ادامه می‌دهیم تا زمانی که هد درنهایت عدد متفاوتی یعنی 1 را بخواند. وقتی دوباره جدول را بررسی می‌کنیم، قانون جدیدی پیدا می‌کنیم: اگر با 1 مواجه شدید، به حالت q2 بروید که حالت رد است. ماشین متوقف می‌شود و به سوال اولیه «آیا 0001 صفر است» پاسخ «نه» می‌دهد.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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