هو الوصول إلى أسطر أقل نصف مرحامة؟

Question

على افتراض أن لدينا برامج $ p_1 $ و $ p_2 $ وأرقام سطرين $ n_1 $ و $ n_2 $ . هل $ p_1 $ الوصول $ n_1 $ في خطوات حسابية أقل من $ p_2 $ يصل $ n_2 $ ؟ من خلال التخفيض من وقف، من الواضح أن هذا ليس مناسبا، لكنني أعتقد أنه شبه مرسوم.

للقيام بذلك، أود بناء مترجم، وهذا ينفذ $ p_1 $ و $ p_2 $ في وقت واحد خطوة بخطوة وحساب الخطوات لكل برنامج. بمجرد $ p_1 $ يصل $ n_1 $ ، أقارن عدد الخطوات إلى $ n_2 $ والعودة TRUE إذا كانت أقل. إذا $ p_2 $ تصل إلى $ n_2 $ أولا، أعود FALSE. في حالة عدم وجود برنامج يصل إلى $ n_1 $ أو $ n_2 $ ، لا يحدث شيء (بعد نصف التسمم).

Answer 1

انها فقط نصف مرحاض إذا كنت مشكلة قرارك بعناية فائقة.وعليك أن نتحدث بهذه الطريقة في مثل هذه الحالة التي لا تصل إليها كلا البرنامجين أبدا $ n $ s موجودة في فئة الرفض.منذ $ \ INFTY <\ INFTY $ غير محدد / غير محدد سأذكر صراحة هذه الحالة في مشكلة قرارك.

بخلاف ذلك، نعم إنه صحيح.يتوقف جهازك إذا كان $ P_1 $ أو $ p_2 $ haltts (عرض الوصول إلى $ n $ مجرد حالة توقف أخرى) ويوفر الإجابة الصحيحة في مثل هذا السيناريو.إذا قمت بتصحيح المشكلة أعلاه، فما عندما لا $ P_1، PE_2 $ توقف أنت في حالة رفض وبالتالي يسمح لك أبدا بوقفها أبدا.