حل تمرین نظریه محاسبات/فصل چهارم/حل تمرین ۴-۲۱

ویکی‎کتاب، کتابخانهٔ آزاد

حل تمرین ۴-۲۱

تمرین[ویرایش]

فرض کنید 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