وقف المشكلة الثابتة آلة تورينج و المدخلات ثابتة

Question

ومن المعروف أن وقف المشكلة غير مقرر حتى عندما نصلح إما آلة تورينج $م$ أو المدخلات $w$.

ماذا لو أننا ثابت سواء الجهاز و الإدخال?I. e., هو decidable كل الثابتة آلة تورينج $M_0$ و كل المدخلات ثابتة $w_0$ أن $M_0$ سيتم وقف على $w_0$ كما مدخلات ؟

Answer 1

ومن المعروف أن وقف المشكلة غير مقرر حتى عندما نصلح إما آلة تورينج $م$ أو المدخلات $w$.

عليك أن تكون أكثر حذرا حول هذا البيان.هذا ليس صحيحا على أي إصلاح آلة تورينج $م$ أن وقف المشكلة $ ext{وقف}_M$ (تحديد المدخلات $w$ إذا $م$ ويوقف على $w$) هو غير مقرر.على سبيل المثال ، إذا $م$ هو الجهاز الذي دائما يوقف, يمكننا بسهولة تقرر $ ext{وقف}_M$ فقط من خلال إخراج "نعم".

ربما أرادت أن تقول الحقائق التالية التي صحيحا:

1. هناك آلة تورينج $م$ هذه المشكلة $ ext{وقف}_M$ (تحديد المدخلات $w$ إذا $م$ ويوقف على $w$) هو غير مقرر.

2. للجميع الكلمات $w$, المشكلة $ ext{وقف}_w$ (تحديد المدخلات $م$ إذا $م$ ويوقف على $w$) هو غير مقرر.

ولا سيما حقيقة 1, يمكننا أن نأخذ $م$ أن تكون عالمية آلة تورينج.

ماذا لو أننا ثابت سواء الجهاز و الإدخال?I. e., هو decidable كل الثابتة آلة تورينج $M_0$ و كل المدخلات ثابتة $w_0$ أن $M_0$ سيتم وقف على $w_0$ كما مدخلات ؟

نعم المشكلة يصبح مسلي decidable.تعريف اللغة $ ext{وقف}_{M_0, w_0}$ أن تكون المشكلة من تحديد ما إذا كان $M_0$ ويوقف على $w_0$.ولكن لاحظ أن هذه المشكلة لم يعد لديه أي معلومات أن الجواب يعتمد على كل الأمور أن الجواب قد تعتمد على ($M_0$ و $w_0$) هي الآن ثابتة ، أيجزء من تعريف اللغة ، وليس جزءا من المدخلات.هذا يعني أن الجواب هو "نعم" أو "لا".حتى نتمكن مسلي تقرر هذه المشكلة إما عن طريق استخدام برنامج الذي يقول دائما "نعم" ، أو برنامج الذي يقول دائما "لا".

هذا هو شرك مشترك حول أوروبا: هو فقط من المفيد أن نسأل ما إذا كانت المشكلة هي decidable أو لا عندما يكون عدد ممكن من المدخلات هو لانهائي. إذا كان هناك فقط بشكل محدود عدد ممكن من المدخلات ، تصبح كل المشاكل decidable.كنت قد سألت عما إذا كان هناك مشكلة مع 1 فقط ممكن الإدخال (فارغة المدخلات) هو decidable و الجواب على ذلك هو نعم دائما.