"إشكالية" عدم وقف مدخلات آلة تورنج

Question

دعونا نبدأ هذا السؤال من خلال تحديد على آلة تورينج, مجموعة من الكلمات لا وقف على.تعريف: $P(M)=\{w\في\سيغما^*|M$ لا وقف على $w \}$

ونحن نعلم أن $وقف$ المشكلة $إعادة\setminus R$ - وهكذا كل TM $م$ الذي يحسب $وقف$ لديه كلمة لا وقف على.هـ $P(M) e\emptyset$.

ومن هذا ينشأ (بسيطة) السؤال:

$س(1):$ "مشكلة غير مقرر إذا و فقط إذا كان كل TM الذي يحسب له غير فارغة 'مشكلة' مجموعة $P(M)$?" $ ^{س\مساحة(1)}$

وعلاوة على ذلك, دعونا نلاحظ أن $وقف$ المشكلة ونحن نعلم أن تعطى $م$ أن يحسب ذلك ، هناك عدد لانهائي من المدخلات سوف أبدا من وقف على (لا تشجع على التفكير لماذا هذا هو الحال ، قبل الشروع في ما بعد)

لذا وبالمثل قد نريد أن نسأل أنفسنا (قليلا) أصعب نسخة من السؤال الأول.

$س(2):$ "مشكلة غير مقرر المنتدى كل TM $م$ الذي يحسب له $|P(M)|=\aleph_0$?" $ ^{س\مساحة(2)}$

وعلاوة على ذلك - دعنا نسأل أقوى السؤال:

$س(3):$ "إذا $L$ هو غير مقرر, ونحن سوف لا يزال تكون قادرة على العثور على محدود مجموعة من آلات تورينج $M_1,...,M_n$ أن حساب $L$ و قد $\bigcap_{ك\الفضاء=\space0}^nP(M_k)$ محدودا ؟ ماذا عن لانهائية مجموعة من آلة تورنج أن تلبية هذا؟" $ ^{س\مساحة(3)}$

و هدفنا النهائي (نصف مفتوحة) السؤال:

$س(4):$ "ماذا يمكن أن نفهم تورينج عن آلات إشكالية مجموعات?"

Answer 1

لذا دعونا نبدأ في معالجة تلك المشاكل.كملاحظة جانبية, لقد رتبت الأسئلة بحيث كل سؤال يستخدم الجواب من أحد قبل ذلك (و هذا تقريبا تبدو تافهة جدا أن تبدأ مع $:$P).

$A(1):$ هو تافهة جدا من التعريف.إذا $L$ هو غير مقرر ثم لا يوجد أي آلة تورينج أن يحسب ذلك و دائما توقف ، وبالتالي جميع آلات تورينج أن حساب $L$ لديك $P(M) e\emptyset$.الاتجاه الآخر هو أيضا بسيط مثل هذا واحد.

$A(2):$ دعونا نفترض $L$ هو غير مقرر.إذا كان هناك آلة تورينج $م$ الذي يحسب $L$ وقد محدود $P(M)$, ثم دعونا نبني الجهاز الجديد $\hat M$ مثل أن يكون $P(\hat M)=\emptyset$ على النحو التالي (على المدخلات $w$):

• إذا رفض $w \في P(M)$ (وهذا ممكن لأن $P(M)$ هو محدود)
• وإلا العودة $M(w)$

هذا الجهاز الجديد ، وقف كل $w\في P(M)$, ولكن لأن كل $w\لافي P(M)$ أنه سيتم تشغيل $م$, و هو ضمان أنه سيتم وقف على ذلك (وإلا لكان في $P(M)$) لدينا الجديد $\hat M$ دائما يوقف ولا تقبل $L$ - وبالتالي يتعارض مع الافتراض.الاتجاه الآخر هو ببساطة المستمدة من $A(1)$.

$A(3)$:بالنسبة محدود مجموعات من آلة تورنج ، $M_1 ، ...M_n$ ونحن سوف تظهر أن من المستحيل أن يكون محدود $\bigcap_{ك\الفضاء=\space0}^nP(M_k)$ ولكن غير مقرر $L$.دعونا نفترض نحو تناقض هذا لا عقد.فقط في $A(2)$, فإننا سوف نبني $\hat M$ - ولكن الآن ما يكفي لبناء مثل أن $P(\hat M)=\bigcap_{ك\الفضاء=\space0}^nP(M_k):$

• تشغيل $M_1(w) ، M_2(w), ...,M_n(w)$ في موازاة ذلك
• تقبل إذا كان أي واحد منهم المقبولة.

الآن من الواضح لماذا $\hat M$ تقبل $L$.السماح $w\لافي P(\هات م)$, ثم هناك بعض $1\le k\le n$ مثل أن $M_k(w)$ أوقفت ، وبالتالي $w\لافي\bigcap_{ك\الفضاء=\space0}^nP(M_k)$.السماح $w\في ص(\هات م)$, ثم لم تتوقف على أي $M_k$, وهكذا $w\في ص(M_k)$ للجميع $k$.وخلصت $P(\hat M)=\bigcap_{ك\الفضاء=\space0}^nP(M_k)$ محدودة وبالتالي من $A(2)$ لا يمكن أن توجد.

فيما يتعلق لانهائية مجموعات من آلة تورنج ، هذا ممكن بالتأكيد.فقط تحدد لكل $w\في \سيغما^*$ الجهاز $M_w$ أن يقبل $L$ ولكن أيضا يوقف على $w$ (على غرار بناء في $A(2)$).ثم $w\لافي P(M_w)$ لذلك $w\لافي \bigcap_{\hat w} P(M_\قبعة w)$ وبالتالي ليس هذا فقط $\bigcap_{\hat w} P(M_\قبعة w)$ محدودة أيضا فارغة.

$A(4):$ السماح $L$ هو غير مقرر ، $M_1 ، M_2...$ هي آلة تورنج الذين يقبلون $L$ و تقاطع "إشكالية تعيين" محدودة.إذا نظرنا إلى وظيفة $f:\mathbb{N} ightarrow\سيغما^*$ تعريف $f(k)=\langle M_k angle$ ثم هو لا محسوب.هذا يلي من $A(2)$ لأنه إذا كان محسوب, كنا قادرين على إنشاء آلة تورينج $\hat M$ مع $P(\hat M)=\bigcap_k P(M_k)$

فكرة أخرى كنت قد بدأت في التفكير في ما يحدث عندما نتحدث عن اثنين لغات أو أكثر بدلا من واحد في وقت واحد.السماح $M_1$ تكون آلة $L_1$ و $M_2$ بالنسبة $L_2$.ثم يمكننا تعريف الجهاز $م$ بالنسبة $L_1\bigcap L_2$ أو $L_1\bigcup L_2$ مع:

$P(M) = P(M_1)\bigcup P(M_2)$ (ملاحظة هذا أيضا يمكن أن يثبت إغلاق خصائص في $\mathcal R$)

أو إذا $L_1\دلتا L_2$ محدودة ثم نحن إشكالية مجموعات من آلات لغات هي نفسها الى حد كبير(على كل آلة $م$ في أي واحد منهم يمكن أن نجد آلات $M'_1 ، م'_2$ لاثنين آخرين اللغات مع نفس إشكالية تعيين)

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

أخيرا!أعتقد (ولكن لا تزال غير متأكد) يمكننا الحصول على نتائج مماثلة (ولكن مع المزيد من القيود) الوقت تعقيد التحليل إذا عرفنا $P(M, t)$ الوقت constructible $t(n)\قه log(n)$ كما مجموعة من الكلمات $م$ لا وقف على داخل $t(n)$ الخطوات التالية.في هذا التعريف هناك مشكلة صعبة من الثوابت ، حتى في أصعب أن تظهر النظريات من خلال تحديد آلات جديدة (كما أنها قد تفعل أكثر قليلا فقط العمل المستمر من شأنها أن تجعل بعض كلمة أدخل إشكالية مجموعة كبيرة-O تدوين هنا هو إلى حد ما معنى مختلف الثوابت)

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