اَبا اِباد

سمت‌ راست آلن تورینگ ریاضیدان بزرگ انگلیسی، سمت چپ بندیکت کامبربچ بازیگر نقش آلن تورینگ در فیلم بازی تقلید

ماشین تورینگ

در فیلم زیبای بازی تقلید (The Imitation Game) محصول سال ۲۰۱۴ به کارگردانی مورتن تیلدام کارگردان نروژی، بخشی از زندگی حرفه‌ای ریاضیدان بزرگ قرن بیستم، آلن تورینگ به نمایش در می‌آید.

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

ماشین تورینگ در واقع یک ماشین فرضی است که آلن تورینگ اولین بار در سال ۱۹۳۶ آن را ارائه کرد.

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

ماشین ما وقتی بالای هر خانه قرار بگیرد، می‌تواند سه کار انجام دهد:

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

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

مثلا بگوییم 00 یعنی عدد 0، 01 یعنی عدد یک و 11 یعنی عدد دو.

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

پی‌نوشت: بد نیست این را هم اضافه کنم که آلن تورینگ جزو دگرباشان جنسیتی بود و از بابت قانون وقت انگلستان مبنی بر ممنوعیت همجنس‌گرایی، ناچار شد در سال ۱۹۵۳ بین زندان رفتن و هورمون درمانی، هورمون درمانی را انتخاب کند. او در اثر عوارض ناشی از هورمون درمانی، دچار افسردگی شدید شده و یک سال بعد در سال ۱۹۵۴ دست به خودکشی زد و این مغز متفکر در سن ۴۱ سالگی درگذشت.

– اَبا اِباد
تصویر بالا: سمت‌ راست آلن تورینگ ریاضیدان بزرگ انگلیسی، سمت چپ بندیکت کامبربچ بازیگر نقش آلن تورینگ در فیلم بازی تقلید. در پشت تصویر سمت چپ، نوارها و مکانیزم توضیح داده شده در مثال فوق دیده می‌شود.

 

ماشین تورینگ
مدل ساده‌ای از ماشین تورینگ

دیدگاه‌ خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *