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

محاسبات یک مفهوم آشنا است که اکثر ما به طور شهودی آن را درک می کنیم. تابع را بگیرید f(x) = x + 3. وقتی x سه است، f(3) = 3 + 3. شش. آسان. بدیهی است که این تابع قابل محاسبه است. اما برخی از توابع چندان ساده نیستند، و تعیین اینکه آیا می توان آنها را محاسبه کرد، چندان آسان نیست، به این معنی که ممکن است هرگز پاسخ نهایی را به ما ندهند.

در سال 1928، ریاضیدانان آلمانی دیوید هیلبرت و ویلهلم آکرمن سؤالی به نام مشکل Entscheidungsproblem ("مشکل تصمیم گیری"). با گذشت زمان، سؤال آنها به تعریف رسمی از محاسبه پذیری منتهی می شود، تعریفی که به ریاضیدانان اجازه می دهد به انبوهی از مسائل جدید پاسخ دهند و پایه و اساس علم کامپیوتر نظری را بنا نهاد.

این تعریف از دانش آموز 23 ساله ای به نام آلن تورینگ گرفته شد که در سال 1936 نوشت: یک مقاله اولیه که نه تنها مفهوم محاسبات را رسمیت بخشید، بلکه یک سؤال اساسی در ریاضیات را ثابت کرد و پایه فکری اختراع رایانه الکترونیکی را ایجاد کرد. بینش بزرگ تورینگ این بود که پاسخی مشخص به پرسش محاسباتی در قالب یک ماشین انتزاعی ارائه کند که بعدها توسط مشاور دکتری او، آلونزو چرچ، ماشین تورینگ نام گرفت. این انتزاعی است زیرا از نظر فیزیکی به عنوان یک وسیله ملموس وجود ندارد (و نمی تواند). در عوض، این یک مدل مفهومی از محاسبات است: اگر ماشین بتواند یک تابع را محاسبه کند، آنگاه تابع قابل محاسبه است.

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

بهترین راه برای درک ماشین تورینگ، در نظر گرفتن یک مثال ساده است. بیایید یکی را تصور کنیم که به ما بگوید آیا یک ورودی داده شده عدد صفر است یا خیر. ما از عدد ورودی 0001 همراه با نمادهای خالی (#) استفاده خواهیم کرد، بنابراین "#0001#" قسمت مربوطه نوار ما است.

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

اکنون ما به دنبال قاعده ای هستیم که برای این شرایط اعمال شود. یکی را پیدا می کنیم که می گوید: "در حالت q1 بمانید و سر یک سلول را به سمت راست ببرید." این ما را در همان موقعیت قرار می دهد (در حالت q1، خواندن "0")، بنابراین ما به حرکت به سمت راست ادامه می دهیم تا زمانی که سر در نهایت یک عدد متفاوت، 1 را بخواند.

وقتی دوباره جدول را بررسی می کنیم، یک قانون جدید پیدا می کنیم: "اگر با یک 1 مواجه شدیم، انتقال به q2، که یک حالت "رد" است." دستگاه متوقف می‌شود و به سؤال اصلی «آیا '0001' صفر است؟» «نه» پاسخ می‌دهد؟

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

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

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

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

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

تنها چند سال پس از اینکه کورت گودل ثابت کرد که ریاضیات است ناقص استچرچ و تورینگ با این کار نشان دادند که برخی از مسائل در ریاضیات غیرقابل تصمیم گیری هستند - هیچ الگوریتمی، هر چند پیچیده، نمی تواند به ما بگوید که آیا پاسخ مثبت است یا خیر. هر دو ضربات مخربی برای هیلبرت بود که امیدوار بود ریاضیات پاسخ‌های آرمانی و مرتبی داشته باشد. اما شاید همینطور باشد: اگر یک راه حل کلی برای مشکل Entscheidungs ​​وجود داشت، به این معنی بود که همه مسائل در ریاضیات را می توان به محاسبات مکانیکی ساده تقلیل داد.

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

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

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

این ماشین‌های انتزاعی شاید بهترین شواهدی باشند که نشان می‌دهد پرسیدن سؤالات اساسی می‌تواند یکی از مفیدترین کارهایی باشد که یک دانشمند می‌تواند انجام دهد.