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

حل تمرین ۴-۲۱
==تمرین==
فرض کنید A یک زبان تشخیص پذیر تورینگ شامل توصیف زبان‌های تورینگ <div style="direction: ltr;">
L = { <M<sub>1</sub>>, <M<sub>2</sub>>, ... }
</div>
بوده که هر M<sub>i</sub> تصمیم پذیر باشد. ثابت کنید که بعضی زبان‌های تصمیم پذیر در D وجود دارند که با هیچ کدام از تصمیم گیرنده‌های M<sub>i</sub> که توصیف آن‌ها در A ظاهر شده‌است قابل تصمیم گیری نیستند.

==حل==
از روش قطری سازی برای مشخص کردن D استفاده می‌کنیم. ... ,<M<sub>1</sub>>, <M<sub>2</sub>> را خروجی یک شمارنده برای A در نظر می‌گیریم. اگر {..., s<sub>1</sub>, s<sub>2</sub> } <math>\sum=</math> لیستی ار تمام رشته‌های روی الفبا باشد.  الگوریتم D مانند زیر است.
   
۱ - i اندیس w روی لیست تمام رشته‌ها است در نتیجه s<sub>i</sub> = w.

۲ - <M<sub>i</sub>> را روی ورودی w اجرا می‌کنیم.

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

D تصمیم گیرنده‌است به این دلیل که <M<sub>i</sub>> تصمیم گیرنده‌است. ولی D در شمارش A وجود ندارد زیرا که با تمام M<sub>i</sub>‌ها روی ورودی S<sub>i</sub> تفاوت دارد.

مرجع :http://www.cs.vassar.edu/~cs240/solutions/assn07-solution.pdf
[[رده:حل تمرین نظریه محاسبات]]