میشه یکی در مورد این سوالات توضیح بدهد؟ این دو تست مربوط به سال ۸۴ و ۸۶ علوم کامپیوتر می‌شود.
![[تصویر: 153434_1_1379086554.jpg]](https://img.manesht.ir/153434_1_1379086554.jpg)
![[تصویر: 153434_2_1379086554.jpg]](https://img.manesht.ir/153434_2_1379086554.jpg)
ممنون دوست عزیز از وقتی که برای جواب دادن گذاشتید.
مشکل من بیشتر notation بود. با مفهوم reduction (تقلیل) از Theory of Complexity آشنا هستم.
اول اینکه خلاف نظر شما فکر کنم زبان‌های RE تحت دسته‌ی Partially Decidable محسوب می‌شوند نه Undecidable (
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
).
A decision problem A is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Problems that are not decidable are called undecidable.
خوب، حالا یه سوال: مسئله‌ی membership برای ماشین‌های تورینگ یک مسئله‌ی undecidable است یا partially decidable؟ خوب، ما اگر یک رشته را به TM بدهیم یا آن را accept می‌کند یا reject و یا اینکه وارد infinite loop می‌شود. پس این مسئله فکر کنم partially decidable است. اما از طرفی مسئله‌ی halting به مسئله‌ی membership تقلیل پیدا می‌کند و ما می‌دانیم که مسئله‌ی halting یک مسئله‌ی undecidable است، پس مسئله‌ی membership هم حتما undecidable است! بالاخره کدام است؟
بعد ببینید اینها را درست تفسیر می‌کنم؟
[tex]L = \left \{ <T> \mid 01 \in L(T) \; and \; T \; is\;a\;Turing\; Machine \right \}[/tex]
اگر با یک قرارداد ماشین‌های تورینگ را کدگذاری کنیم، آنگاه زبان L شامل کدگذاری آن دسته از ماشین‌های تورینگ است که اولا نمایانگر یک ماشین تورینگ می‌باشند و دوما رشته‌ی ۰۱ را قبول می‌کنند. کلید گزینه‌ی ۲ را زده (RE است ولی تصمیم‌پذیر نیست).
[tex]\left \{ <T> \mid \lambda \in L(T) \right \} \leq L[/tex]
اول اینکه کلید زده گزینه‌ی ۲ (بازگشتی نیست).
خوب، این یکی میگه یک زبان داریم که شامل همه‌ی ماشین‌های تورینگ هست که رشته‌ی λ را قبول می‌کنند. خوب، ادامه‌ی جواب این سوال هم برمی‌گرده به سوال اولم که مسئله‌ی membership جزو partially decidable (و درنتیجه RE) است یا undecidable؟
هممم، و یه چیز دیگه که الان من رو به شک انداخت. undecidable یعنی نه decidable باشد و نه partially decidable؟ درست می‌گم؟
خوب، من فهمیدم مشکلم چی بود. قضیه همون چیزی هست که اون آخر شک کرده بودم. مسائل Undecidable مسائل partially decidable رو هم پوشش می‌دهند. یعنی halting در واقع یک مسئله‌ی partially decidable هست (
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
). عجب سوتی‌ای دادم!
Partially decidable problems and any other problems that are not decidable are called undecidable
* راستی، چرا انجمن مانشت از BBCode مروبط به ltr (برای متن Left to right) پشتیبانی نمی‌کنه؟