اصلاً اتوماتون یعنی چه؟!!

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

…

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

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

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

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

(که احتمالاً فرمان حمله به لندن است!)

روشی که آلمانی‌ها برای رمزگذاری به‌کار می‌گرفتند کمی پیچیده بود. اما برای نخستین نمونه، فرض می‌کنیم که همه‌ی پیام‌های معنی‌دار دشمن با یک «-» پایان می‌یابند، به همین سادگی! مثلاً پیام بالا معنی‌دار است، اما پیام زیر بی‌معنی است:

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

شکل ۱

بیایید اسم این ماشین را «اتوماتون» بگذاریم. راستش را بخواهید این اتوماتون خیلی پیچیده نخواهد بود و لازم است فقط یک چیز را بررسی کند: اینکه آیا آخرین سیگنالی که گرفته‌ایم «-» است؟ دقت کنید که ممکن است پیام تمام نشده باشد و باز هم سیگنال دریافت کنیم. اما اگر آخرین سیگنال دریافتی «-» باشد و پیام تمام شود آنگاه پیام معنی دار است. در این اتوماتون کلاً دو حالت داریم، اینکه آخرین سیگنالی که گرفته‌ایم «.» است (حالت A) یا «-» (حالت B). می‌توانیم این حالت‌ها را با دایره نشان دهیم(شکل ۱).

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

شکل ۲

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

شکل ۳

هر بار که سیگنال جدیدی می‌آید، بسته به سیگنال، ممکن است حالت ماشین ما عوض شود. مثلاً اگر در حالت A باشیم و سیگنال «-» را دریافت کنیم باید به حالت B برویم (تغییر حالت بدهیم). (چرا؟) این تغییر حالت‌ها را با پیکان‌هایی نشان می‌دهیم. هر یک از پیکان‌ها برچسبی دارد که نشان می‌دهد چه سیگنالی موجب این تغییر شده است.

شکل ۴

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

شکل ۵