ماشین تورینگ

در این ویدئوی آموزشی به بررسی ماشین تورینگ و انواع آن خواهیم پرداخت.

کیفیت فیلم بصورت پیش فرض بر روی حالت low تنظیم شده است و شما می توانید با استفاده از تنظیمات موجود، این آموزش را با بالاترین کیفیت مشاهده نمایید.

شما می توانید با استفاده از گزینه “متن فیلم”، متن مربوط به حل سوال را مشاهده کنید.

//******************************************************************************************************************************************//

پیشنهاد می شود قبل از مشاهده این آموزش، مروری بر مبحث ماشین‌های متناهی و ماشین‌های پشته ای داشته باشید. شما در پایان این آموزش با ماشین تورینگ و چگونگی عملکرد آن آشنا خواهید شد.

ماشین تورینگ، ماشینی است که برای گرامرهای سطح نوع صفر و یک مورد استفاده قرار می گیرد.

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

ماشین تورینگ M یک هفت تایی مرتب است که به صورت روبرو نشان داده می شود:

•   مجموعه حالات ماشین
• الفبای نوار است.
•   الفبای  ورودی ماشین  می باشد به گونه ای که زیر مجموعه ای از الفبای نوار هم  محسوب می شود.
•   تابع انتقال
• وضعیت شروع
• نشان دهنده محدوده و ابتدا و انتهای نوار حافظه و
•   مجموعه حالات نهایی ماشین (حالت پذیرش) می باشد.

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

ماشین تورینگ انواع مختلفی دارد…

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

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

ماشین فقط خواندنی یا read only نوع دیگری از ماشینهای تورینگ است. در این نوع از ماشین ها نیازی به تغییر محتویات نوار نیست.

و نوار نامحدود از هیچ طرفی محدودیت ندارد.

ماشین تورینگ با دیگر ماشین ها تفاوت هایی دارد که در جدول روبرو مشاهده می کنید.

حال می خواهیم برای تابع روبرو یک ماشین تورینگ طراحی کنیم. همانطور که گفته شده اعداد باید بصورت یکانی در نظر گرفته شوند.

در تابع f ابتدا باید عمل مقایسه انجام گیرد.

اگر x بزرگتر از y باشد ،خروجی حاصل تفریق  x با y است.

اگر x کوچکتر مساوی با y باشد حاصل تابع x+y است.

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

اعداد در سیستم بصورت یکانی در نظر گرفته می شود مثلاً عدد ۳ را به صورت ۱۱۱ در نظر می گیریم. همچنین از علامت ها برای نشان دادن ابتدا ، آخر و بین دو عدد استفاده می شود.که می توان از خود عملگر ریاضی برای جدا کردن دو عدد استفاده کرد.

ابتدا عمل مقایسه را پیاده سازی می کنیم.

همانطور که گفته شد اعداد فقط با ۱ نشان داده می شود، پس برای مقایسه کردن، باید تعداد یک ها مقایسه شود . بنابراین به ازای هر ۱ از x باید یک عدد ۱ از y هم حذف شود یا به عبارتی با علامت ¨ جایگزین شود.

 پس برای اینکه x بزرگتر از y باشد باید تعدادی ۱ در سمت چپ از نوار باقی بماند و اگر در سمت راست ۱ باقی ماند y بزرگتر از x است و اگر در هر دو طرف تمام ۱ها با ¨ جایگزین شود، x با y  برابر می باشد.

ابتدا ماشین تورینگی طراحی می‌شود که به ازای xهای بزرگتر مساوی با y وارد وضعیت نهایی شود یا به عبارت دیگر جواب بله بدهد.

در ابتدای حرکت وقتی که هد نوار به اولین ۱ رسید آن را با ¨ جایگزین کرده و به حرکت به سمت راست ادامه داده و تمام ۱‌ها را طی می کند تا به ¨ به عنوان عنصری که دو عدد را از هم جدا می کند برسد و تغییر وضعیت دهد.

در وضعیت q2 ، موقعیت هد در عدد y است ،پس ابتدا تمام ۱ ها را می خواند تا به علامت ¨ برسد سپس هد به سمت چپ حرکت کرده و تا اولین عدد ۱ را می بیند با ¨ جایگزین کند و به وضعیت q4 برود. در این وضعیت باید دوباره نوار با حرکت به سمت چپ ابتدا تعدادی ۱ سپس یک علامت ¨ و سپس تعدادی ۱ که بیانگر محدوده x هست را طی کند تا به اولین ¨ برسد و دوباره شروع به جایگزین کردن ۱ با ¨ از سمت x و سپس از سمت y کند.

با این شرایط اگر قرار باشد که ماشین به ازای xهای بزرگتر از y وارد وضعیت final شود پس باید در زمانی که در وضعیت q3 قرار دارد یعنی در ابتدای محدوده y دیگر هیچ یکی برای حذف کردن وجود نداشته باشد یا به عبارتی حرفی که از نوار می خواند علامت ¨ باشد که در تصویر با رنگ آبی مشخص شده است. و اگر برابر باشند یعنی در نوار فقط علامت ¨ باشد می تواند به وضعیت نهایی برود.

در شرایطی که x با yبرابر است تمام یک های x با یک های y حذف می شود و در نوار فقط ¨ می ماند پس، از وضعیت q0 به q7 می رود که با پیکان قرمز رنگ نشان داده شده است.

عمل مقایسه x کوچکتر از y  هم به همین صورت پیاده سازی می شود، فقط با این تفاوت که  x حتما باید از y کوچکتر باشد پس باید y حداقل یک عدد ۱ بیشتر از x داشته باشد. تغییرات با رنگ قرمز نشان داده شده است.

عمل تفریق شبیه به عمل مقایسه کردن است یعنی به ازای هر یک از y یک عدد ۱ از x باید حذف شود.

ماشین بعدی طراحی ماشین جمع کننده است.

در عمل جمع همانطور که در مثال نشان داده شده است برای جمع دو عدد ۲ و ۳ باید به تعداد یک های ۳ به یک های عدد ۲ اضافه شود.

با جایگزین کردن علامت + با ۱ و از آخر هم ۱ با ¨ حاصل جمع بدست می آید.

در گراف عملکرد جمع را مشاهده می کنید.