كيفية إثبات شبه decidable = يمكن التحقق منها ؟

Question

لغة L هو التحقق المنتدى هناك مكان اثنين المسند R ⊆ Σ∗ × Σ * على هذه R هو محسوب ، بحيث لكل x ∈ Σ∗:x ∈ L ⇔ يوجد y بحيث R(x, y)

لغة شبه decidable المنتدى هناك بعض آلة تورينج أن يقبل كل سلسلة في L و إما أن ترفض أو حلقات على كل سلسلة لا L.

كيف يمكننا أن تبين أن فئة من شبه decidable المشاكل هو ما يعادل فئة من التحقق منها مشاكل ؟ أو أنها لا ؟

Answer 1

الواضح لماذا شبه decidable اللغة يمكن التحقق منها ($w$ سيكون الجهاز حساب التاريخ على $x$).الآن, ونحن سوف تظهر بطريقة أخرى:

السماح $V(x,w)$ يكون متحقق بالنسبة $L$.تعريف $M(x)$ كما الخوارزمية التالية:

1. السماح $S$ تكون مجموعة فارغة (من آلة تورينج محاكاة)
2. كل $w\في\سيغما^*:$
   3. إضافة جديدة مضاهاة $V(x,w)$ إلى $S$.
   4. كل مضاهاة $E\S:$
      5. حساب خطوة واحدة $E$.إذا ، $E$ قبلت ، ثم قبول.

هذه الخوارزمية هو الصحيح, لأنه إذا $x\in L$ ثم هناك بعض $w\في\سيغما^*$ مع $V(x,w)=True$ وبالتالي الخوارزمية سوف تقبل.

إذا الخوارزمية مقبولة ، ثم يجب أن يكون هناك بعض $w\في\سيغما^*$ حيث $V(x,w)=True$ وهكذا $x\in L$ من خلال التعريف