ساعدني في فهم مشكلة آلة تورينج هذه المتعلقة $ A_ {TM} $

Question

أنا فيزياء / c.s. طالب وكان يكافح من خلال هذه المشكلة بالذات لبضعة أيام الآن. لذلك المهمة هي كما يلي:

---

النظر في اللغات التالية:

$ \ hspace {20pt} l_1={\ langle m \ rangle \، | \، l (m)= a_ {tm} \} \\ \ Hspace {20pt} l_2={\ langle m \ rangle \، | \، l (m)=overline {a_ {tm}} \} $

هل هذه مرسومة؟ إثبات قرارك.

$ a_ {tm} $ يتم تعريفها على أنها $ \ {\ {\ langle m، w \ rangle \ ،، | \، \ text {m هو tm and m يقبل w} \} $

---

لذلك أولا، أحاول فهم اللغة الأولى $ l_1 $ . ما هو بالضبط سوف يعني $ l_1 $ حتى تكون مرسومة؟ أفهم لماذا $ a_ {tm} $ غير صالحة، ولكن ما الذي سيقرر $ l_1 $ فعلا تفعل؟

أشعر أنني أعرف بالفعل الحل للمشكلة الثانية ولكنني أود أن أعرف ما إذا كانت غريزة الأمعاء صحيحة. لذلك منذ $ \ overline {a_ {tm}} $ لا يتغاضي التعرف عليه، وهذا يعني أن $ M $ مع $ l (m)=overline {a_ {tm}} $ غير موجود / فارغ. وبالتالي $ l_2=expryset $ وهذا سهل جدا.

Answer 1

حل اللغة $ l_1 $ يعني معرفة كل TM إذا كان شبه تحديد $ a_ {tm} $ مشكلة.

غريزة الخاص بك هو الصحيح - فهو فارغ وبالتالي حلول. إذا لم تكن فارغة من قبل أي فرصة، فمنها نظرية الأرز التي لم تكن حائزة