حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۲۱
حل تمرین ۴-۲۱
تمرین
ویرایشفرض کنید A یک زبان تشخیص پذیر تورینگ شامل توصیف زبانهای تورینگ
L = { <M1>, <M2>, ... }
بوده که هر Mi تصمیم پذیر باشد. ثابت کنید که بعضی زبانهای تصمیم پذیر در D وجود دارند که با هیچ کدام از تصمیم گیرندههای Mi که توصیف آنها در A ظاهر شدهاست قابل تصمیم گیری نیستند.
حل
ویرایشاز روش قطری سازی برای مشخص کردن D استفاده میکنیم. ... ,<M1>, <M2> را خروجی یک شمارنده برای A در نظر میگیریم. اگر {..., s1, s2 } لیستی ار تمام رشتههای روی الفبا باشد. الگوریتم D مانند زیر است.
۱ - i اندیس w روی لیست تمام رشتهها است در نتیجه si = w.
۲ - <Mi> را روی ورودی w اجرا میکنیم.
۳ - اگر قبول یا رد کرد ورودی قبول است.
D تصمیم گیرندهاست به این دلیل که <Mi> تصمیم گیرندهاست. ولی D در شمارش A وجود ندارد زیرا که با تمام Miها روی ورودی Si تفاوت دارد.
مرجع :http://www.cs.vassar.edu/~cs240/solutions/assn07-solution.pdf