الحد من وقف$ دولار A_{TM}$

Question

أنا أعرف الحد من $A_{TM}$ إلى $وقف$.ولكن هو التخفيض التالية من $وقف$ إلى $A_{TM}$ الصحيح ؟

نحن نبحث عن مجموع محسوب وظيفة $f$ رسم الخرائط من $وقف$ إلى $A_{TM}$.التالي TM $F$ يحسب الحد $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

أعتقد الخط if T accepts or rejects, *accept* هو الصحيح ، ولكن سيكون من الرائع إذا كان شخص ما يمكن أن تحقق هذا.

تحرير:وجدت الشرائح التالية ، ولكن لا أعتقد البناء في الصحيح: http://slideplayer.com/slide/13791105/

Answer 1

هناك عدة مفاهيم "الحد من الفقر." كنت قد وصفت بشكل صحيح العديد من تخفيض واحد من $وقف$ إلى $A_{TM}$.الحد لقد ربط (أكثر تحديدا الرابط هنا) بدلا من ذلك الحقيقة-جدول الحد.هذه هي أعم الأشياء (حتى نتيجة الخاص بك هو أقوى).كل بدوره تندرج في إطار أوسع بكثير من مفهوم تورينج الحد.

في حين أن العديد واحد تخفيضات عموما الافتراضي الفكرة في نظرية التعقيد ، تورينج التخفيضات الناتجة درجة هيكل هي الافتراضية في computability theory.لاحظ أنه إذا كان كل ما تريد القيام به هو إثبات undecidability من بعض ، تورينج الحد من بعض معروف-إلى-أن-غير مقرر مجموعة كافية.

---

أولا دعونا صراحة نذكر التعاريف من اللغات المشاركة:

• $A_{TM}=\{\langle M,w angle:M$ توقف ويقبل على المدخلات $w\}$.

• $وقف=\{\langle M,w angle:M$ ويوقف على المدخلات $w\}$.

المقترح الخاص بك الحد من $وقف$ إلى $A_{TM}$ هو الصحيح:نظرا $م$, يمكننا computably بناء الجهاز الجديد $\hat{M}$ الذي يقبل على وجه التحديد تلك السلاسل التي $م$ ويوقف.(في الأساس مجرد استبدال كل "رفض" في الدول $م$ من قبل "قبول" الدول.)

---

الآن دعونا ننظر في غيرها من الحد الذي يرتبط (أكثر تحديدا الرابط هنا).

في الأساس, بدلا من الذهاب إلى "وقف جميع الدول تقبل" المرتبطة الحجة ترى على حدة:

• الجهاز الأصلي ،

• "العكس" الجهاز الذي يقبل بالضبط عندما الأصلي واحد يرفض والعكس بالعكس.

جوابا بالإيجاب على أي حال في $A_{TM}$ يضمن الإجابة بالإيجاب على الجهاز الأصلي في $وقف$.

من على قمة رأسي وأنا لا أرى أي سبب للقيام بذلك بدلا من اتبع الحجة ، خاصة لأنه ينتج أضعف نتيجة ، ولكن هذا هو الصحيح و هو ما يكفي لإثبات الأوسع المطالبة في الشرائح ، وهي أن $A_{TM}$ هو غير مقرر.