أوراكل موجود

أو قد توجد خوارزمية عامة لمشكلة إيقاف التشغيل.
ولكن ، كما هو الحال دائما ، هناك فروق دقيقة.
إذا كانت مهتمة ، أطلب القط.

مقدمة

في عام 1936 ، أثبت آلان تورينج أنه لا توجد خوارزمية عامة تحلل الخوارزميات الأخرى وتشير إلى ما إذا كان البرنامج سوف يتعطل أم لا.

أود أن أقوم فورًا بنقل كل العناصر الإلكترونية ووصف المصطلحات التي أستخدمها لي حتى لا يكون هناك أي فهم.

يتجمد البرنامج - ستعمل الخوارزمية على مقدار لا حصر له من الوقت ، بغض النظر عن سرعة تنفيذ الأوامر والحوسبة المتوازية. بغض النظر عن حجم الكمبيوتر العملاق الذي نحن عليه ، ستعمل الخوارزمية دائمًا على مقدار لا حصر له من الوقت.

تشغيل برنامج في وقت محدد - ستنهي الخوارزمية على أي جهاز حساباتها بغض النظر عن حجمها الضخم. على سبيل المثال ، إذا استمرت خوارزمية 300 مليون سنة ، فإن هذا لا يعني أنها معلقة ، بل تحتاج فقط إلى تشغيل 300 مليون سنة على الموارد الحالية وينتهي دائمًا.

الآن يمكنك المتابعة.

يمكن وصف دليل تورينج على النحو التالي: هناك أوراكل S (خوارزمية) معينة يتم عندها تقديم وصف للخوارزمية N وبيانات الإدخال X. يتوقف البرنامج ويعود 1 إذا لم تتوقف الخوارزمية N ، يتلقى X عند الإدخال.

لا يتوقف البرنامج عن غير ذلك ، إذا توقفت الخوارزمية N بعد تلقي الإدخال X. إذا قمنا بتغذية وصفنا لأنفسنا بأوراكل ، فسوف يكون هناك تناقض وستتناقض الخوارزمية مع نفسها. يمكن الاطلاع على التفاصيل على الويكي .

أوراكل موجود لكنه يحتاج إلى أخ

أنت لست مرتبكًا من حقيقة أن أوراكل يجب أن يتجمد إذا توقفت الخوارزمية التي يقوم بتحليلها ، فأنا مرتبك بشكل مباشر من هذه الحقيقة ، لذلك لإثبات أننا سنصحح تمامًا اختتام أوراكل. اسمح للأوراكل بالعودة 1 أو 0. حسنًا ، إذن ، أنت تسأل ، لم يتغير شيء إذا كتبنا على الكود الزائف:

If ((N)==0){
While (true){
}
} 

, , :
, , :

S1 0 1 0 1 , .

S2 0 1 , . 1 1 , 0 . 0 , 1 .

, . .

, , . , , .

, . , .

:

If ((N)==0){
While(true){
}
}

If ((N)==0){
While(true){
}
}

.

.
, . , . - , .

, , . , .