لماذا لا تثبت نظرية العودية وجود مجموعة محدودة غير قابلة للتقرير؟

Question

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

$ a_r: = { langle m rangle | m = r land m text {يقبل "foobar"} } $

يفترض $د$ يقرر $A_R$. $ر:=$ على أي إدخال:

1. بواسطة نظرية العودية، احصل على الوصف الخاص بك $\langle R angle$
2. يجري $د$ على $\langle R angle$
3. افعل عكس ما $د$ يقول.فإذا رفض، قبل.فإذا قبلت، ارفض.

$R$ يتناقض مع ما $د$ يقول عنه $R$.لذا $د$ لا يمكن أن يكون صاحب القرار.(أي.لو $د$ يقبل $R$, $R$ يجب أن تقبل "foobar"، ولكن $R$ سوف يرفض كافة السلاسل.لو $د$ يرفض $R$, $R$ يجب أن ترفض "foobar"، ولكن $R$ سيقبل جميع السلاسل).

ولكن $A_R$ يمكن أن تحتوي فقط $R$, $A_R = \emptyset \lor A_R = \{\langle R angle\}$.وفي كلتا الحالتين، فهو محدود، لذلك $A_R$ أمر قابل للتقرير.

إذن ما الخطأ في الحجة الأولى؟بعض الأفكار تخطر ببالي:

• أنا أفقد تفاصيل مهمة من خلال تقديم حجة غير رسمية.
• شيء غريب في العلاقة العودية بين المبنى $A_R$ والمرجعية $د$.(ربما يمكن تجنب ذلك عن طريق تضييق نطاقه إلى المجموعة الفرعية من TMs بطول R، والذي يمكننا "تخمينه" قبل إنشاء R - وسيظل محدودًا)
• الخدع المنطقية (على غرار مفارقة الكذاب)

لكنني لا أرى بالضبط ما هي المشكلة.

توضيح تفسيري للخطأ كمرجع إضافي:

تبدو الحجة كما يلي:

1. نظرا لقرار تعسفي ل $A_R$, ، يمكننا بناء TM $R$.
2. منح $R$, ، نحن نبني $A_R$.
3. ومن ثم يمكننا الحصول على التناقض.لذلك ليس هناك من يقرر $A_R$.

هذا تعميم، ونأمل أن يكون خطأً أكثر وضوحًا.وتخمين طول $R$, ، كما اقترح سابقًا، لا يعمل أيضًا - لأن المُقرر التعسفي له طول تعسفي.

Answer 1

حجتك "تعود إلى الوراء".

لاحظ أن تعريفك لـ $R$ يعتمد على $د$ (خطوة $2$).هذا يعني أنك لا تستطيع استنتاج ذلك لا الآلة تقرر $A_R$, ، مجرد ذلك $د$ على وجه التحديد لا.

في الأساس، ما كتبته يبدو كالتالي:

• مطالبة:هناك بعض $x$ بحيث لا $ص$ يفعل [المهمة التي تنطوي على $x$].

• دليل:اختيار بعض $ص$, ، نحن نبني $x$ مثل ذلك $ص$ لا يفعل [المهمة التي تنطوي على $x$].

وهذا غير صحيح.

---

قد يكون من المفيد النظر في حجة من نفس "الشكل" ولكن حول موضوع أكثر تحديدًا.

• مطالبة:هناك عدد طبيعي $ن>1$ والذي لا يقبل القسمة على أي عدد أولي $p$.

• دليل:تحديد رئيس الوزراء $p$, ، يترك $ن=ع+1$.ثم $ن$ لا يقبل القسمة على $p$.

إن الطبيعة الدقيقة لقابلية اتخاذ القرار غالبًا ما تجعل الأسئلة المتعلقة بها تبدو أكثر تعقيدًا مما هي عليه في الواقع، وأعتقد أن هذا هو الوضع.

---

تجدر الإشارة إلى أنه يمكن تطبيق نظرية العودية هنا للتوضيح شئ ما - على وجه التحديد، أن $A_R$ليست كذلك بشكل موحد قابل للتقرير.

على وجه التحديد، لنفترض أن لدي بعض الوظائف الحسابية الإجمالية $و$.بواسطة نظرية العودية أستطيع أن أصنع آلة $R$ مثل ذلك $R$ يتصرف كما تصفه $د=و(ص)$, ، و حينئذ $و(ص)$ لا أستطيع أن أقرر $A_R$.هذا يعنى:

بينما لكل $R$ هناك بعض $د$ الذي يقرر $A_R$, ، لا يوجد قابلة للحساب طريقة للعثور على مثل هذا $د$ منح $R$.

هذا ليس مفاجئًا - فالنتيجة نفسها تتبع ببساطة عدم إمكانية حل مشكلة التوقف - ولكنها مثال مهم لكيفية استخدام نظرية التكرار لإثبات نتائج قابلية القرار غير المنتظمة حتى عندما تكون كل لغة من اللغات المعنية قابل للتقرير.

Answer 2

إنها نقطة رصاصة الثانية - شيء غريب في العلاقة العودية.

الحجة تحاول إظهار تناقض من خلال إظهار لغة محدودة غير قابلة للكشف عنها.

بمعنى آخر، تحتاج الحجة إلى إظهار أن هناك موجود لغة محدودة $ l $ بحيث بالنسبة لكل قرار $ d $ ، هناك بعض المدخلات $ W $ مثل $ D $ تقرر بشكل غير صحيح سواء $ w \ in l $ .

المشكلة هي أنك تقوم بتبديل الكميات: أنت تختار قرارا $ D $ أولا، ثم تعرض لغة (عن طريق تحديد $ r $ هذا يعتمد على $ D $ ) وقول أن $ D $ لا يقرر $ a_r $ بشكل صحيح. للحصول على تناقض، لا يمكن أن تعرف لغتك مقدما، سيتم محاكمة القرار.

أود أن أضيف ذلك أثناء $ a_r $ أمر مثير للاهتمام لكل $ r $ (كما هو مجموعة محدودة)، إذا قمت بإجراء $ r $ معلمة إدخال، لم تعد المجموعة الناتجة جديلة.