ممنون دوست عزیز از وقتی که برای جواب دادن گذاشتید.
مشکل من بیشتر notation بود. با مفهوم reduction (تقلیل) از Theory of Complexity آشنا هستم.
اول اینکه خلاف نظر شما فکر کنم زبان‌های RE تحت دسته‌ی Partially Decidable محسوب می‌شوند نه 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 هست (
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
). عجب سوتی‌ای دادم!


* راستی، چرا انجمن مانشت از BBCode مروبط به ltr (برای متن Left to right) پشتیبانی نمی‌کنه؟