ماشین‌های تورینگ

 «ماشین‌های تورینگ» عنوان مقاله‌ای است که نویسنده‌ی آن، دکتر رابرت سالمون (1) و مترجم آن آقای غلامرضا یاسی‌پور می‌باشد و در شماره‌ی 69 رشد برهان دوره‌ی متوسطه، بهار 1390 چاپ شده است.
متن کامل این مقاله به شرح زیر است:
آلن تورینگ2، ماشین‌هایی را توصیف کرد که بیان می‌کنند برحسب محاسبه، چه چیز ممکن است و چه‌چیز ناممکن است.
ماشین‌های تورینگ3، رایانه‌ای است که غیر از لوازم اصلی، عاری از ملزومات دیگر است. وسیله‌ای است که به‌جای فلز و پلاستیک بودن، ایده‌ای مجرد از یک ماشین است. کار این ماشین بررسی نواری با طول نامتناهی است که با OS و IS علامت‌گذاری شده است. این نوار، از زیر هدی می‌گذرد که عدد مورد نظر را می‌خواند، و آن‌گاه دو کار انجام می‌دهد: یکی روی عدد مورد بحث و دیگری روی نوار:
1. 1 را به 0 یا 0 را به 1 تغییر می‌دهد، یا عدد را دست‌نخورده باقی می‌گذارد.
2. نوار را یک مرحله جلو می‌برد، یک مرحله عقب می‌برد یا دست‌نخورده باقی می‌گذارد.
ماشین تورینگ را می‌توان طوری طراحی کرد که جمع، تفریق یا هر عمل اساسی حساب را انجام دهد. درواقع می‌تواند هر عمل حسابی پیچیده را انجام دهد. با یک مرحله جلوتر رفتن، هر عمل محاسبه می‌تواند با ماشین تورینگ انجام گیرد.
به نظر می‌رسد که باید برای هر عمل، ماشین تورینگی جداگانه موجود باشد. اما در اقدامی شگفت‌انگیز، تورینگ نشان داد که برای هر عمل، به ماشینی جداگانه نیاز نداریم. در عوض، یک ماشین تورینگ عمومی موجود است که می‌تواند مانند هر ماشین تورینگ دیگر عمل کند. پس این ماشین عمومی می‌تواند هر عمل محاسبه‌پذیر را به انجام برساند. این مطلب به کمال تورینگی موسوم است.
دستاورد مهم دیگر، مسئله‌ی ایست است. با در دست داشتن یک ماشین تورینگ، همواره نمی‌توان تشخیص داد که توقف می‌کند یا محاسبه را تا ابد ادامه می‌دهد. این موضوع، محاسبه‌ای هم‌ارز قضیه‌ی گودل است.
در دوران جنگ جهانی دوم، آلن تورینگ، کارهای پر ارزشی در حوزه‌ی رمزگشایی انجام داد.

پی‌نوشت
1. Dr. Robert Solomon
2. Alan Turing
3. Turing Machines