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

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

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

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

به گزارش مجله کوانتا، تعریف مورد بحث زاییده ذهن یک دانش آموز 23 ساله به نام آلن تورینگ بود که در سال 1936 مقاله ای اساسی نوشت که نه تنها مفهوم حساب دیفرانسیل و انتگرال را رسمیت بخشید، بلکه یک سوال اساسی در ریاضیات را نیز به اثبات رساند. و شالوده فکری اختراع رایانه الکترونیکی را تشکیل داد.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

در سال 1945، جان فون نویمان نوعی معماری کامپیوتری به نام معماری فون نویمان را پیشنهاد کرد که مفهوم ماشین جهانی تورینگ را در یک ماشین واقعی پیاده سازی کرد.

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

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

یکی دیگر از انواع قابل توجه و مفیدتر ماشین تورینگ، “ماشین تورینگ احتمالی” است. برخلاف ماشین تورینگ معمولی که برای هر ورودی واکنش خاصی دارد، ماشین تورینگ احتمالی می تواند بر اساس احتمالات واکنش های متعددی داشته باشد. این بدان معناست که دستگاه می تواند نتایج متفاوتی را برای یک ورودی در زمان های مختلف تولید کند. جالب اینجاست که این نوع استراتژی احتمالی می تواند برای برخی مشکلات مفیدتر از یک رویکرد کاملا قطعی باشد.

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

5858