مهم ترین ماشینی که هرگز ساخته نشد - مجله مدیریت ناب

محاسبات مفهومی آشنا است که بیشتر ما به طور شهودی آن را درک می کنیم. تابع (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