معضلة غير قابلة للقرار
في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي معضلة هدفها صنع قرار ما، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة.[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. (ردمك 3-540-72503-2). دُوِي:10.1007/978-3-540-72504-6_49 نسخة محفوظة 23 ديسمبر 2016 على موقع واي باك مشين.
