حل تمرین نظریه محاسبات/فصل سوم/حل تمرین ۳-۱۶

اثبات طرف اول : فرض کنیم که L توسط ماشین تورینگ M تصمیم پذیر باشد.می توان یک شمارنده برای L به نام E ساخت به این شکل که همه رشته‌های ممکن w را به ترتیب الفبا مرور کند و برای هرw، M(w) را شبیه سازی کند.اگر M ، w را قبول کرد که چاپ می‌کند.در هر صورت رشته بعدی از برشمارنده بررسی می‌شود و ادامه پیدا می‌کند. اثبات طرف دوم: فرض کنیم L توسط تورینگ شمارنده‌ای به نام M شمردنی باشد،حال L با ماشین تورینگی که شرح داده می‌شود ، تصمیم پذیر است:برای ورودی w، برای هر خروجی w’ از E چک می‌کنیم که آیا w=w’ ؟اگر برابر هستند ، پذیرفته می‌شود و متوقف می‌شود.در غیر این صورت ، E حرکت می‌کند تا به رشته‌ای برابر با w برسد که پذیرفته می‌شود و متوقف شود و یا به w’’ ای برسد که در الفبا بزرگتر از w باشد که حالت reject و سپس توقف پیش می‌آید و یا E متوقف می‌شود اگر wεL باشد که الگوریتم آن را می‌پذیرد که درست است و اگر w عضو L نباشد ، الگوریتم آن را رد می‌کند چون E رشته‌های بزرگتر از w را می‌شمرد و E هیچ وقت w را تولید نخواهد کرد.