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

B مجموعه ای از زبان‌های تشخیص‌پذیر تورینگ است و می‌دانیم زبان‌های تشخیص پذیر تورینگ شمارا هستند. C نیز مجموعه‌ ای از زبان‌های تصمیم پذیر است و می‌دانیم که مجموعه ی زبان های تصمیم پذیر هم شمارا هستند. پس می‌توان هر کدام را با مجموعه ی N معادل کرد پس هر دو مجموعه را می توان با هم معادل کرد. پس برای هر ماشین در B معادلی در Cوجود دارد.

طرف اول:

B={x|there is a y such that<x,y>eC}if

فرض کنید y یک ماشین تورینگ باشد که رشته ی ورودی x را می پذیردو B یک زبان نیمه تصمیم گرفته شده توسط Mباشد که توسط ماشین M=<M1,M2,...>a پذیرفته میشود.بنابراین برای هر رشته ی ورودی x اگر xeB باشد باید یک ماشین تورینگ محاسباتی y از M روی x موجود باشد.با داشتن x,y می توان نتیجه گرفت که y یک ماشین محاسباتی از M روی x است.پس C={<x,y>|y is an accepting computation of M on x} تصمیم پذیر است.

طرف دوم:

اگر B یک زبان تشخیص پذیر باشد,روی ورودی x با محسوب کردن تمام رشته ها از y,به ازای هر y بررسی می کنیم که آیا<x,y> عضو C هست یا خیر؟ که برای این کار به سادگی می توان یک ماشین تصمیم پذیر برای C ساخت.اگر yی پیدا کردیم به طوری که <x,y> عضو C باشد آن را می پذیرد و Halt می شود.از طرفی می دانیم که هر ماشین تصمیم پذیر یک ماشین تشخیص پذیر تورینگ هم هست.پس قسمت دوم به سادگی اثبات می شود.

‍C is a Turing-recognizable language D is a decidable language The idea is to view y as(the encoding of)an accepting computation og a turing machine on input x. let C be semi-decided by a turing machine M.Then, for every string x,we have xeC iff there exist an accepting computation y of M on x.Given x,y it is easy to decide if y is indeed an accepting computation of M on x.so D={<x,y>|y is an accepting computation of M on x} is decidable.

For converse we can semi-decide C as follow:on input x,enumerate all strings y ,checking for each y if <x,y> e D (using the decider for D)if find a y such that <x,y> in D the accept and halt.