قراءة آلات Turing التي لا تحرك أبدا رؤوسهم بعد أي سلسلة إدخال

Question

$ l_1={\ langle m، w \ g \ rangle: m \ text {هو tm لا يحركها أبدا رئيسه الماضي سلسلة الإدخال} W \} $
$ l_2={\ langle m \ rangle: m \ text {هو tm لا يتحرك أبدا رئيسه الماضي أي سلسلة إدخال} \} $

النظر في اللغتين أعلاه.أريد أن أعرف أي منها لا يمكن أن يكون.

أنا أعلم أن $ l_1 $ $ M $ لا يحتوي فقط على كمية محدودةالتكوينات المحتملة مع سلسلة الإدخال $ W $ ، حتى نتمكن من إنشاء آلة تورينج (TM) للتحقق من خطوة واحدة بعد تجاوز عدد المجموعات وتحديد.

ومع ذلك، ل $ l_2 $ ، هل يمكننا أن نفعل ذلك؟أشعر وكأنني $ l_2 $ غير قابل للتكرار، لأننا نستطيع أن يكون هناك حد للتكوينات المحتملة.

Answer 1

مشكلة توقف، $ \ mathsf {توقف} $ يقلل إلى $ \ overline {l_2} $ .

إعطاء tm $ t $ and incut $ W $ ، قم بإنشاء TM جديد $ n $ ذلك على أي إدخال من الطول $ n $ ، يحاكي $ T $ على المدخلات $ W $ for خطوات $ N $ الخطوات ثم تتوقف إلا عن ذلك $ t $ توقف من أي وقت مضى قبل $ n $ الخطوات، $ N $ سوف تحرك رأسها إلى اليمين إلى الأبد.

هناك فجوة في التخفيض أعلاه. عندما $ n $ يحاكي $ T $ على $ W $ for خطوات $ n $ ، قد يخرج من المدخلات عندما يتحرك اليسار (نفترض أن المدخلات يتم وضعها على يمين الأصل، الموضع الأولي ل رأس $ N ، شامل). يمكن حل هذه الفجوة من خلال خدعة كلاسيكية من "ترجمة الشريط". عندما تكون المحاكاة حول الانتقال إلى يسار الأصل، دع $ N $ ترجمة التيار الشريط خلية واحدة إلى اليمين. ثم $ N $ يذهب إلى الأصل، كما لو كانت الخلية إلى يسار الأصل. وبهذه الطريقة، سوف نتأكد من أن $ N $ لن تنتقل أبدا من سلسلة الإدخال طالما أن $ t $ على $ W $ لا توقف. (لتمكين $ n $ للتعرف على الأصل، يجب عليك دائما وضع علامة الأصل مع رمز "مركب" يحكي أيضا رمزه الأصلي. على سبيل المثال، إذا كان الأصلي الرمز عند الأصل هو $ $ ، $ n $ يجب تغييره إلى $ A_O $ ، رمز ليس $ $ ولكن يشير إلى $ $ . يتم استخدام الرموز "المركبة" أيضا عند $ n $ يترجم محتوى الشريط.)

منذ $ \ mathsf {halt} $ غير صالحة للحساس، $ \ overline {l_2} $ ليست حلول. لذلك، $ l_2 $ غير صالحة للاستحقاق.