معضلة غير قابلة للقرار

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي معضلة هدفها صنع قرار ما، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة.[1][2]

انظر إلى مبرهنات عدم الاكتمال لغودل.

مراجع[عدل]

  1. ^ Matiyasevich، Yuri (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (باللغة Russian). 191: 279–282. 
  2. ^ "The Undecidability of the. Generalized Collatz Problem", in Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. (ردمك 3-540-72503-2). doi:10.1007/978-3-540-72504-6_49 نسخة محفوظة 23 ديسمبر 2016 على موقع واي باك مشين.


Midori Extension.svg
هذه بذرة مقالة بحاجة للتوسيع. شارك في تحريرها.