سلام. اجازه بدید همین اول کار بگم که اگه میخواید طوطی واری این ارسالو بخونید، همی الان بیخیالش شید، چون وقتتون رو تلف کردید. باید با دقت بخونید تا متوجه شید
ببینید ماشین تورینگ یه نواره و یه هد خوندن و نوشتن. همین و بس. تو مدل معمولیش فرض شده که نوار از دو طرف نا محدوده. این نوارمون قاعدتاً سلول سلول هم هست دیگه و هر سلولش میتونه یه علامت رو توی خودش ذخیره کنه. هد با قرار گرفتن رو هر سلول میتونه علامتی که توشه رو بخونه و توش بنویسه (یعنی محتوای سلوله رو تغییرش بده) و بعد از این عمل میتونه به چپ یا راست حرکت کنه. تموم شد... فقط یه نکته خیلی مهم هس که هیچ وقت نباید فراموش کنید. به ماشین تورینگ پذیرنده گفته میشه. میدونید چرا؟؟؟ "چون که روی نوار یه سری چیزا هس. بعد ماشین تورینگ رو روش اِعمال میکنیم ببینیم آیا روی نوار همون چیزی هس که ما میخوایم یا نه. اگه بود که به حالت پایانی میرسیم. اگه نبودم که هیچ. یعنی میشه اینجوری فرض کرد که میان یه نوار میدن به شما و میگن تعیین کن ببینیم رو این نواره فلان عبارت هس یا نه.بعد شما ماشین طراحی میکنید ببینید محتوای نوار با همون فلان عبارته میخونه یا نه. حالا در ادامه بهتر متوجه میشید.
ماشین تورینگ رو با یه ۷ تایی نشون میدن. به این صورت: [tex]M={Q , \Sigma , \Gamma , \delta , q0 , ,q_{f}}[/tex]
Q مجموعه حالتای ماشینه. دقیقاً مث حالتای ماشین منظم.
سیگما الفبای زبونه
گاما الفبای نواره (یکم تحمل کنید، در ادامه معلوم میشه چیه)
دلتا رو که خودتون میدونید، تابع تغییر وضعیته.
q0 که حالت شروعه
+ علامت محدود کننده نواره. علامت خیلی مهمیه و در واقع یکی از اعضای گاماس.
qf هم یه مجموعه از حالات نهاییه. دقت کنید که یه مجموعس. میتونه تهی باشه و یا میتونه کل حالات ماشین باشه.
خب، تا اینجا حله؟؟؟

تابع تغییر وضعیت خیلی مهمه. یعنی همون دلتا. مهمه و به این شکله که (روی گراف تصور کنید) ورودیش یه حالت و یه علامت از الفبای نواره و خروجیش هم اینه که به یه حالت دیگه میره، علامتی که داخل سلوله رو تغییر میده و در نهایت میتونه به سمت چپ یا راست حرکت کنه.
گرفتید چی شد؟ کلاً تابع تغییر وضعیت به این شکل در میاد: [tex]\delta (Q \times \Gamma) = Q \times \Gamma \times (Left / Right)[/tex]

مثلاً میتونیم به عنوان یه تابع تغییر وضعیت بنویسیم [tex]\delta (q_{0} , a) \rightarrow (q_{1} , x , R)[/tex]
این معنیش این میشه که اگه تو وضعیت q0 هد خوندن و نوشتن رو سلولی قرار بگیره که a داخلش باشه، باید بره به وضعیت q1 و از همون سلول a رو حذف کنه و به جاش x بذاره و در آخر به سمت راست (R راسته و L چپ) حرکت کنه.
تموم شد. حالا باز میتونیم یه دونه از همین تابع تغییر وضعیت بنویسیم برای این وضعیتی که حالا اومدیم توش. یعنی بعد از اینکه تابع بالا رو نوشتیم، میتونیم n تا تابع دیگه هم بنویسیم.
خب، حالا به عنوان یه مثال کامل، سعی کنید این مثال رو حل کنید...
[tex]\left\{\begin{matrix} \delta (q_{0} , a) \rightarrow (q_{1} , a , R) & & \\ \delta (q_{1} , b) \rightarrow (q_{1} , b , R) & & \\ \delta (q_{1} , ) \rightarrow (q_{f} , , L) & & \end{matrix}\right.[/tex]

اول سعی کنید خودتون حلش کنید. خب، خط اول معنیش مشخصه، داره میگه تو حالت اول اگه روی نوار a دیدی بجاش a بنویس (یعنی تغییرش نده) و برو به حالت q1 و یه سلول به سمت راست حرکت کن. الان میشه تصور کرد که a روی نواره و دقیقاً یه خونه مست چپ هد قرار داره. توی حالت q1 هم هستیم. درسته؟ این از خط اول. فقط حواستون باشه که اگه اول کار (یعنی وقتی تو حالت q0 هستیم) رو نوار b نوشته باشه ماشین هیچ وقت به حالت پایانی نمیرسه ها... متوجه اید که؟
حالا تو حالت q1 هستیم. حالا میریم تو توابع تغییر وضعیت نگا میکنیم ببینیم از q1 آیا به جایی میریم یا نه. همون طور که مشخصه تو سطر دوم نوشته شده که اگه تو حالت q1 باشیم و توی سلولی که هد روشه b باشه، باید این b رو تغییر نده و به سمت راست حرکت کنه. یعنی اگه n تا b ببینه باید ردشون کنه.
میتونید نوار رو تصور کنید؟ اگه یه a رو نوار باشه و در ادامش n تا b باشه، همین جور b ها رو رد میکنه و تو حالت q1 باقی میمونه. ولی هنوز نرسیدیم به حالت پایانی.
حالا سطر آخر توابع تغییر وضعیتو نگا کنید... نوشته که تو حالت q1 اگه هیچی ندیدیم (علامت + همون nullه) هم میتونیم به حالت پایانی بریم.
پس کلاً اگه رو نوار عبارت abbb نوشته شده باشه، با اعمال این توابع به حالت پایانی میریم. اگه a نشوته شده باشه هم همینطور. یعنی در کل این ماشین تورینگ [tex]ab^{*}[/tex] رو میپذیره. درسته؟ به همین سادگی. کار با ماشین تورینگ دقت و تجربه زیاد میخواد. همه کار میشه انجام داد یا این توابع تغییر وضعیت. همه اعمال ریاضی و ... .

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