هل $ \ {w ~ | ~ \ forall x \ in t (m_v): | w |> | x | ~ \} $ مرحل؟

Question

أريد أن أسأل إذا $ \ {w | \ forall x \ in t (m_v): | w |> | x | \} $ هو حلولV هو مؤشر آلة تورينج عشوائية ولكن ثابتة مع $ | T (m_v) | <\ isty $ .

فكرتي: انها مشتركة نصف مرحامة منذ أقرب وقت يمكنني العثور على $ x \ in t (m_v) $ مع $ |X | \ GEQ | W | $ لقد أظهرت أن هذا sepcific w ليس في المجموعة.أعتقد أنه ليس نصف مرحامة، حيث يمكن أن يكون هناك دائما $ x \ in t (m_v) $ وهو أطول من ث.لذلك أعتقد أيضا أن المشكلة غير قابلة للكشف عنها.

هل أشرف على شيء ما؟

Answer 1

نعم، أنت تفتقد شيئا ما.

الحجة الأولى أن هذه اللغة هي صحيحة صحيحة. ومع ذلك، فإن الثانية هو الخطأ (وليس مكتوب رسميا. لا يمكن أن يتكون دليل رسمي من هذه الحجج، فهي فقط للحدس عادة).

الآن لإظهار سبب حلها بالكامل: نحن نعرف أن $ | T (M_V) |= C <\ INFTY $ . الآن، نظرا لأن هذا أصغر ثابتا من اللانهاية، يجب أن يكون هناك $ x_0 \ in t (m_v) $ والتي $ | X_0 | $ هو أطول من الكلمات في $ t (m_v). $

الآن، قم ببناء آلة turing التي تقبل $ W $ IFF $ | w |> | x_0 | $ .

منذ $ x_0 دولار هو الأطول، ثم إذا كان $ | W |> | x_0 | $ $ \ forall x \ in t (m_v): | w |> | x_0 | \ ge | x | $ ، وبالتالي $ W $ في لغتك. الآن، إذا $ | W | \ le | x_0 | $ ، ثم من الواضح $ W $ ليس في لغتك.

هكذا $ W $ هو في لغتك IFF $ W $ مقبولة بواسطة آلة turing نحن بنيت.