الارتباك وقف المشكلة

Question

تبين أن المشكلة قابلة للحل.نظرا برنامجين مع مدخلات المعرفة بالضبط واحد منهم توقف ، تحديد أي توقف.

يتيح P يكون البرنامج الذي يحدد من سيتم توقف البرنامج.

P(Program x,Program y){

    if(x will be halted)

          then return 1;

    else

           then return 2;
}

وبما أننا نعرف بالضبط واحد منهم سوف يكون توقف ، إن 1 ثم برنامج x سيتم توقف.Otherwiae برنامج y سيتم توقف.

ثم نبني برنامج جديد اتصل D

D(X,Y){

     if(P(X,Y) == 2)

         D will halt;

      else

         while(1)//D will not halt;

  }

يتيح S يكون aritbrary البرنامج.

حتى إذا كان لدينا د(D,S)

إذا د ستوقف ثم د لن تتوقف

إذا د لن توقف ثم وقف D

فإنه impiles تناقض نفسها كما وقف المشكلة.

ولكن السؤال ذكرت أنها قابلة للحل.

Answer 1

أن تبدأ مع أهمية ملاحظة جانبية:ما هي المدخلات $X$ و $Y$ أنها سوف توقف ؟ تحتاج إلى تحديد مدخلات محددة للأجهزة من أجل مسألة أن تكون محددة (على سبيل المثال ، فإن السؤال قد يكون "نظرا $X,Y$ أين بالضبط واحد ينهي على $\ابسيلون$, ، الذين توقف." أو ربما "نظرا ...حيث واحد بالضبط دائما يوقف على نفسها كمدخل...")

أرى ما أشكل عليك هناك.المشكلة هي في الواقع قابلة للحل:في $P$ تحاكي كل $X$ و $Y$ والإجابة لمن وقف الأولى.

المشكلة في الحل الخاص بك هو أن أحد المدخلات $P$ يجب أن يكون $X,Y$ حيث بالضبط واحد منهم يوقف و الآخر لا.

لذا السليم المدخلات $D$ يجب أن تكون مناسبة المدخلات $P$.لاحظ الآن اتصلت $د(D,S)$.للتأكد من أن $D$ سيعود إخراج الصحيح يجب أن يكون مناسب المدخلات:واحد فقط من $D$ أو $S$ ويوقف!ولكن...إذا $S$ توقف ثم $D$ أيضا التوقفات ليس هذا هو الصحيح المدخلات $P$, و لذلك أيضا لم السليم المدخلات $D$.وبالتالي لا يمكن الاعتماد على الانتاج من $د(D,S)$ كما أنها قد لا تكون صحيحة