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

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

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

مراجع
  1. Matiyasevich, Yuri (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (باللغة الروسية). 191: 279–282. الوسيط |CitationClass= تم تجاهله (مساعدة)
  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 على موقع واي باك مشين.


    • بوابة رياضيات
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.