Кіріспе
Есептеу теориясындағы түсінік. Есептеу теориясында, егер бір санды кіріс ретінде қабылдап, шекті уақыт ішінде (берілген санға байланысты болуы мүмкін) тоқталып, сол сан жиынға жата ма, жатпай ма екенін дұрыс анықтайтын алгоритм болса, онда табиғи сандар жиыны есептелуге жарамды, рекурсивті немесе шешімді деп аталады. Есептелуге жарамсыз жиын есептелмейтін немесе шешілмейтін деп аталады. Есептелуге жарамды жиынтардан гөрі жалпырақ класс – есептелуге болатын (көбінесе) жиынтар, оларды жартылай шешімді жиынтар деп те атайды. Мұндай жиын үшін, сан жиынға кіретінін дұрыс анықтайтын алгоритмнің болуы жеткілікті; алгоритм жиынға кірмейтін сандарға жауап бермеуі мүмкін (бірақ қате жауап бермеуі керек).
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not. A set which is not computable is called noncomputable or undecidable. A more general class of sets than the computable ones consists of the computably enumerable (c. e.) sets, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.
Ресми анықтама
Натурал сандардың ішкі жиыны есептелетін деп аталады, егер осы жиынның элементтеріне сәйкес келетін толық есептелетін функция болса. Яғни, жиын есептелетін болады, егер және тек қана оның индикатор функциясы есептелетін болса.
Қасиеттері
Егер A есептеуге болатын жиын болса, онда A-ның толықтығы да есептеуге болатын жиын болады. Егер A және B есептеуге болатын жиындар болса, онда A ∩ B, A ∪ B және Кантор жұптастыру функциясы бойынша A × B-нің бейнесі есептеуге болатын жиындар болады. A есептеуге болатын жиын, егер және тек қана A және A-ның толықтығы екеуі де есептеу арқылы саналатын (с. е.) болса. Толық есептеуге болатын функция бойынша есептеуге болатын жиынның кері бейнесі есептеуге болатын жиын болады. Толық есептеуге болатын биекция бойынша есептеуге болатын жиынның бейнесі есептеуге болады. (Жалпы алғанда, есептеуге болатын функция бойынша есептеуге болатын жиынның бейнесі есептеу арқылы саналатын, бірақ міндетті түрде есептеуге болатын емес). A есептеуге болатын жиын, егер және тек қана ол арифметикалық иерархияның деңгейінде болса. A есептеуге болатын жиын, егер және тек қана ол өспейтін толық есептеуге болатын функцияның диапазоны немесе бос жиын болса. Өспейтін толық есептеуге болатын функция бойынша есептеуге болатын жиынның бейнесі есептеуге болады.