في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي معضلة هدفها صنع قرار ما، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة.[1][2]
انظر إلى مبرهنات عدم الاكتمال لغودل.
مراجع
- Matiyasevich, Yuri (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (باللغة الروسية). 191: 279–282.
- "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. (ردمك ). doi:10.1007/978-3-540-72504-6_49 - تصفح: نسخة محفوظة 23 ديسمبر 2016 على موقع واي باك مشين.