دليل على أن اللغات هي تورينج التعرف على IFF محسوبة

Question

سؤال صغير للغاية على هذا الدليل، والذي وجدت باسم نظرية 3.21 في Sipser، وفي ملاحظات محاضراتي.

في الاتجاه "P> فقط، نفترض أن آلة تورينج $ M $ تدرك بعض اللغات $ l $ . نحن ندرج جميع السلاسل في الأبجدية الإدخال (في ترتيب معجم، تقول) ك $ s_1، s_2، s_3، \ dots $

ثم نبني عداد $ e ذلك لكل $ i= 1،2،3، \ dots $ يدير ببساطة $ m $ for $ i $ $ الخطوات on كل إدخال $ s_1، s_2، s_3، \ dots، s_i $ ؛ ثم يطبع أي $ s_j $ والتي يتم قبولها بواسطة $ M $ . $ e $ هو ما نحتاج إليه.

الآن، منذ أن أعرف أن السلاسل محدودة، لماذا يجب أن أركض $ m $ for $ i $ الخطوات على الأول $ i $ strings، عندما أستطيع تشغيله فقط على $ I $ سلسلة؟ يبدو وكأنه مضاعفات غير ضرورية.

p.s. سئل سؤال آخر عن ذلك، لكنه تناول أدنى شك في: سؤال "فقط إذا كانت" جزء من نظرية النظرية "هي تورينج التعرف على IFF بعض العدادات تعددها."

Answer 1

إذا قمت بتشغيل $ m $ على $ i $ $ -string ثم قد لا تتوقف أبدا، لذلك الخوارزمية الخاصة بك سوف تكون عالقة.الفكرة هي أنه في حالة $ M $ لا تتوقف على $ i $ $ -string، قل بعد خطوات $ J $ ، ثم سنرى ذلك بمجرد الوصول إلى $ \ max (i، j) $ السلسلة.