(۱۵ اسفند ۱۳۹۴ ۰۹:۱۶ ب.ظ)Iranian Wizard نوشته شده توسط:  سلام.
ماشین تورینگ غیر قطعی M که برای هر ورودی نهایتا متوقف می شود با زبان L مفروض است
همه گزینه های زیر صحیح هستند،بجز:

۱-اگر [tex]x\notin L[/tex] لزوما ماشین در هر محاسبه پاسخ خیر (No) می دهد.
۲-لزوما متمم L (زبان [tex]L'[/tex]) دارای یک ماشین تورینگ قطعی است که برای هر ورودی متوقف می شود.
۳-لزوما L دارای یک ماشین تورینگ قطعی است که برای هر ورودی متوقف می شود.
۴-اگر برای ورودی x ماشین پاسخ خیر (No) بدهد لزوما [tex]x\notin L[/tex] .

با تشکر.

قضیه : برای هر ماشین تورینگ غیر قطعی ، ماشین تورینگ با حالت قطعی برای آن وجود دارد
توضیح : طبق صورت سوال ماشین تورینگ در این سوال برای هر ورودی متوقف میشود ( یا Yes یا No )، این تعریف ما رو یاد زبان های بازگشتی یا REC میندازه که هر ورودی بهش بدیهم توقف میکنه، زبان L هم داریم که اگه به ماشین بدیم حتما Yes رو میده به ما
پس برای اینکه ماشین تورینگ پاسخ Yes به ما بده ورودی باید subset L باشه این توصیفات بریم سراغ گزینه ها.
میشه شکل زیر :


گزینه ۱) اگر [tex]x\notin L[/tex] صد رد صد ماشین به ما پاسخ No میده ( قسمت آبی رنگ ) ( درست )
گزینه ۲ ) زبان های REC تحت عمل مکمل گیری بسته هستند .
گزینه ۳ ) قضیه ای که گفتم ( درست )
گزینه ۴ ) اگر ورودی ماشین x باشه ، و ماشین No به ما بدهد صد در صد نمیشه گفت [tex]x\notin L[/tex] . ممکنه عضو L هم باشه ( قسمتی که زردش یکم تیره تره ) ( غلط )

پاسخ تست : گزینه ۴