تز تورینگ

بسمه تعالی

نظریه زبانها – ماشین تورینگ

تر جمه The Church Turing Thesis  

    به دنبال توسعه نظریه محاسبات، چندین مدل از ابزارهای محاسباتی را ارائه می کنیم. آتاماتای متناهی، مدلهای خوبی برای ابزارهای با جافظه کوچک هستند. آتاماتای push down ، مدلهای خوبی برای ابزارهای با حافظه نامحدود هستند که فقط به روش last in first out یا همان LIFO که روش حافظه پشته (stack) است مورد استفاده قرار می گیرند. ما نشان می دهیم که برخی وظایف خیلی ساده  فراتر از قابلیتهای این مدلهاست. ازینرو ، آنها خیلی محدود می شوند تا بتوانند بعنوان مدلهایی از کامپیوترهای همه منظوره  عمل کنند.

    اکنون سراغ مدل خیلی قویتری می رویم که نخستین بار توسط آلن تورینگ (Alan Turing) در سال 1936 میلادی و تحت عنوان ماشین تورینگ ارائه شد. مشابه یک آتاماتای محدود ولی با حافظه ای نامحدود و بدون شرط است و مدل دقیقتری از یک کامپیوتر همه منظوره را ارائه می کند. یک ماشین تورینگ تمام کارهایی که یک کامپیوتر همه منظوره انجام می دهد را انجام می دهد. اما با این وجود، ماشین تورینگ نیز از حل مسائل قطعی عاجز است. در یک نگاه خیلی دقیق، اینگونه مسائل فراتر از محدودیتهای تئوریک در محاسبات هستند.

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

    جهار مورد زیر، تفاوت های اساسی میان ماشین های تورینگ و آتاماتای متناهی است :

1-             یک ماشین تورینگ هم می تواند روی نوار بخواند و هم بنویسد.

2-              هد (head) خواندن و نوشتن می تواند هم به راست و هم به چپ حرکت کند.

3-              نوار، نامحدود است.

4-              حالات ویژه برای پذیرفتن یا رد کردن آثاری فوری دارد.

    به طور غیر رسمی، الگوریتم را اینگونه تعریف می کنیم که مجموعه ساده ای از دستورات ساده برای اجرای برخی وظایف است. الگوریتمها در زندگی روزمره و در ریاضیات نقش بسیاری دارند. اما بطور دقیقتر می توان این فهم شهودی از الگوریتمها را با نظریه ماشین تورینگ ، نشان داد. تاریخچه این امر، به ماجرای مهمی به نام مسائل هیلبرت باز می گردد.           

احمد صفایی