فك شفرة مجموعة قابلة للحساب

في نظرية الحوسبة ، تسمى مجموعة من الأرقام الطبيعية القابلة للحساب أ أو القابلة للتقرير computable إذا كانت هناك خوارزمية تأخذ رقمًا كمدخلات ، وتنتهي بعد فترة زمنية محدودة (ربما اعتمادًا على الرقم المحدد) وتقرر بشكل صحيح ما إذا كان الرقم ينتمي إلى المجموعة أم لا.

المجموعة غير القابلة للحساب تسمى "|غير قابلة للحساب " noncomputable أو غير قابلة للتقرير undecidable.

تتكون فئة المجموعات الأكثر عمومية من المجموعات القابلة للحساب من مجموعات القابلة للحساب ، والتي تسمى أيضًا المجموعات شبه القابلة للتقرير semidecidable sets. بالنسبة لهذه المجموعات ، يلزم فقط وجود خوارزمية تقرر بشكل صحيح متى يكون الرقم في المجموعة ؛ قد لا تعطي الخوارزمية إجابة (لكن ليس الإجابة الخاطئة) للأرقام غير الموجودة في المجموعة.