آلة تورينج التي يمكن أن تتذكر

Question

يتم تعريف آلة Turing الخاصة تماما مثل آلة Turing القياسية، فقط يتم إجراء كل خطوة وفقا لمحتوى الشريط الذي يبدأ من الحافة اليسرى إلى موضع الرأس في الشريط. (وظيفة الانتقال في هذه الحالة تنتمي إلى q x γ * -> q x γ γ {l، r})

أي مما يلي صحيح:

تحتوي كل لغة L على آلة تورينج يقرر L إذا وفقط إذا كان هناك آلة تورينج خاصة تقررت L.

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

ج. A، الإجابات B صحيحة.

د. A، الإجابات B غير صحيحة.

ومسؤولي هو: الجواب الصحيح هو D وأنا لا أستطيع أن أفهم لماذا.

الجواب هو: يمكن تحديد كل لغة بواسطة آلة تورينج خاصة في وقت الإدخال الخطي (O (n) عندما يكون N طول الإدخال). تنتقل وظيفة الانتقال إلى اليمين طالما لم يتم رؤية مساحة فارغة، وبمجرد أن ترى مفاتيح مساحة فارغة لاستقبال أو رفضها وفقا للكلمة المكتوبة على الشريط.

سؤالي هو: كيف يمكنني أن أقرر ما إذا كانت سترفض أو قبول كلمة؟ في النماذج الحسابية الأخرى، مثل PDA، DFA، حددنا وظيفة الانتقال بالمثل، ولا تمت إضافة أي قوة إلى النموذج. لماذا يبدو أن الطاقة تتم إضافة الطاقة إلى النموذج الحسابي نتيجة لتغيير وظيفة الانتقال عندما يتعلق الأمر بآلات Turing؟

شكرا.

Answer 1

إعطاء أي لغة $ l $ هناك آلة تورينج خاصة $ T $ التي تقرر $ l $ في وقت متعدد الحدود.

آلة turing لديها 3 ولايتها: الدول الأولية $ Q_0 $ ، وقبول الدولة $ Q_A $ ورفض الحالة $ Q_R $ . دع $ \ gamma $ يكون الأبجدية الشريط (بما في ذلك الرمز الفارغ $ \ varepsilon $ )، واسمحوا $ \ ألفا x $ تشير إلى محتويات الشريط بدءا من الحافة اليسرى إلى موضع الرأس في الشريط، حيث $ \ ألفا \ في \ gamma ^ * $ و $ x \ in \ gamma $ . كالعادة، سأفترض أن المدخلات مكتوبة تبدأ من بداية الشريط وأن الرأس وضع في البداية في بداية الشريط. يتم تعريف وظيفة الانتقال $ \ delta $ كما يلي:

• $ \ delta (q_0، \ alpha x)= (q_0، x، r) $ إذا كان $ x \ NEQ \ VAREPSILON $
• $ \ delta (q_0، \ alpha x)= (q_a، x، r) $ إذا كان $ x=Varepsilon $ و $ \ alpha \ in l $
• $ \ delta (q_0، \ alpha x)= (q_a، x، r) $ إذا كان $ x=Varepsilon $ و $ \ alpha \ not \ in l $

منذ هناك لغات غير قابلة للتوحيد لآلات Turing العادية، وهذا يعني على الفور أن A و B هي FALSE.

الإجابات D و C غير واضحة. يتحدثون عن "كلا الإجابات" لكنك تعطى 4 دولارات $ الإجابات المحتملة.