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

حل تمرین ۴-۲۱

تمرین

فرض کنید A یک زبان تشخیص پذیر تورینگ شامل توصیف زبان‌های تورینگ

L = { <M₁>, <M₂>, ... }

بوده که هر M_i تصمیم پذیر باشد. ثابت کنید که بعضی زبان‌های تصمیم پذیر در D وجود دارند که با هیچ کدام از تصمیم گیرنده‌های M_i که توصیف آن‌ها در A ظاهر شده‌است قابل تصمیم گیری نیستند.

حل

از روش قطری سازی برای مشخص کردن D استفاده می‌کنیم. ... ,<M₁>, <M₂> را خروجی یک شمارنده برای A در نظر می‌گیریم. اگر {..., s₁, s₂ } $\sum =$ لیستی ار تمام رشته‌های روی الفبا باشد. الگوریتم D مانند زیر است.

۱ - i اندیس w روی لیست تمام رشته‌ها است در نتیجه s_i = w.

۲ - <M_i> را روی ورودی w اجرا می‌کنیم.

۳ - اگر قبول یا رد کرد ورودی قبول است.

D تصمیم گیرنده‌است به این دلیل که <M_i> تصمیم گیرنده‌است. ولی D در شمارش A وجود ندارد زیرا که با تمام M_i‌ها روی ورودی S_i تفاوت دارد.

مرجع :http://www.cs.vassar.edu/~cs240/solutions/assn07-solution.pdf