Сандар жиынының есептеуге келтірілуі, жартылай шешімділік, Тьюрингті тану – бұл информатикадағы маңызды түсініктер. Алгоритмдер мен жиындар туралы біліңіз.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық логика тұжырымдамасы
Mathematical logic concept
Есептеу теориясында S табиғи сандар жиыны есептеуге болатын, рекурсивті саналатын (r. e.), жартылай шешілетін, ішінара шешілетін, тізімделетін, дәлелденетін немесе Тьюрингтік танылатын деп аталады, егер:
In computability theory, a set S of natural numbers is called computably enumerable (c. e.), recursively enumerable (r. e.), semidecidable, partially decidable, listable, provable or Turing recognizable if:
Алгоритм тоқтаған кіріс сандарының жиыны дәл S-қа тең болатын алгоритм бар.
There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.
Немесе, баламалы түрде,
Or, equivalently,
S жиынының мүшелерін тізімдейтін алгоритм бар. Яғни, оның шығысы S жиынының барлық мүшелерінің тізімі болады: s1, s2, s3, … Егер S жиыны шексіз болса, бұл алгоритм мәңгі жұмыс істей береді. Бірінші шарт неліктен кейде «жартылай шешілетін» термині қолданылатынын түсіндіреді. Нақтырақ айтқанда, егер сан жиынтықта болса, оны алгоритмді іске қосу арқылы анықтауға болады, ал егер сан жиынтықта болмаса, алгоритм мәңгі жұмыс істейді және ешқандай нәтиже қайтармайды. «Толық шешілетін» жиын – есептеуге болатын жиын. Екінші шарт «есептеуге болатын» терминінің неліктен қолданылатынын түсіндіреді. Толық сөз тіркесінің орнына c. e. және r. e. аббревиатуралары жиі қолданылады, тіпті баспа материалдарында да. Есептеу күрделілігі теориясында барлық есептеуге болатын жиындарды қамтитын күрделілік класы RE деп белгіленеді. Рекурсия теориясында, кіріктіру бойынша c. e. жиындарының решеті деп белгіленеді.
There is an algorithm that enumerates the members of S. That means that its output is simply a list of all the members of S: s1, s2, s3, If S is infinite, this algorithm will run forever. The first condition suggests why the term semidecidable is sometimes used. More precisely, if a number is in the set, one can decide this by running the algorithm, but if the number is not in the set, the algorithm runs forever, and no information is returned. A set that is "completely decidable" is a computable set. The second condition suggests why computably enumerable is used. The abbreviations c. e. and r. e. are often used, even in print, instead of the full phrase. In computational complexity theory, the complexity class containing all computably enumerable sets is RE. In recursion theory, the lattice of c. e. sets under inclusion is denoted .
Ресми анықтама
Табиғи сандар жиыны S, егер оның домені дәл S-қа тең болатын ішінара есептеуге болатын функция болса, есептеуге болатын тізімдік деп аталады, яғни функция тек қана оның кірісі S жиынының мүшесі болғанда ғана анықталады.
A set S of natural numbers is called computably enumerable if there is a partial computable function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.
Мысалдар
Кез келген есептелетін жиын санауға жарамды, бірақ санауға жарамды әрбір жиын есептелетін емес. Есептелетін жиындар үшін алгоритм кіріс жиынға жатпаса, оны да көрсетуі керек – бұл санауға жарамды жиындардан талап етілмейді. Рекурсивті санауға жарамды тіл – формальды тілдің есептеу арқылы санауға жарамды кіші жиыны. Тиімді ұсынылған аксиоматикалық жүйедегі барлық дәлелденетін сөйлемдер жиыны – есептеу арқылы санауға жарамды жиын. Матиясевич теоремасы бойынша, кез келген санауға жарамды жиын – диофанттық жиын (керісі тривиальды түрде орындалады). Қарапайым жиындар санауға жарамды, бірақ есептелетін емес. Шығармашылық жиындар санауға жарамды, бірақ есептелетін емес. Кез келген өнімді жиын санауға жарамды емес. Есептелетін функциялардың Гёдель нөмірлеуін ескере отырып, жиын (кантор жұптастыру функциясы және көрсеткіш анықталған) есептеулік түрде санауға жарамды (суретті x үшін қараңыз). Бұл жиын тоқтату мәселесін кодтайды, өйткені ол әрбір Тьюринг машинасы тоқтатын кіріс параметрлерін сипаттайды. Есептелетін функциялардың Гёдель нөмірлеуін ескере отырып, жиын есептеу арқылы санауға жарамды. Бұл жиын функция мәнін анықтау мәселесін кодтайды. f функциясы табиғи сандардан табиғи сандарға бөліп берілген болса, f ішінара есептелетін функция болады, егер және тек қана f графигі, яғни f(x) анықталған барлық жұптар жиыны, санауға жарамды болса.
Every computable set is computably enumerable, but it is not true that every computably enumerable set is computable. For computable sets, the algorithm must also say if an input is not in the set – this is not required of computably enumerable sets. A recursively enumerable language is a computably enumerable subset of a formal language. The set of all provable sentences in an effectively presented axiomatic system is a computably enumerable set. Matiyasevich's theorem states that every computably enumerable set is a Diophantine set (the converse is trivially true). The simple sets are computably enumerable but not computable. The creative sets are computably enumerable but not computable. Any productive set is not computably enumerable. Given a Gödel numbering of the computable functions, the set (where is the Cantor pairing function and indicates is defined) is computably enumerable (cf. picture for a fixed x). This set encodes the halting problem as it describes the input parameters for which each Turing machine halts. Given a Gödel numbering of the computable functions, the set is computably enumerable. This set encodes the problem of deciding a function value. Given a partial function f from the natural numbers into the natural numbers, f is a partial computable function if and only if the graph of f, that is, the set of all pairs such that f(x) is defined, is computably enumerable.
Қасиеттері
Егер A және B есептеуге болатын жиынтықтар болса, онда A ∩ B, A ∪ B және A × B (Кантор жұптастыру функциясымен табиғи сандардың реттелген жұбы бір табиғи санға бейнеленгенде) есептеуге болатын жиынтықтар болады. Ішінара есептеуге болатын функция бойынша есептеуге болатын жиынтықтың кері бейнесі есептеуге болатын жиынтық болады. Егер жиынтықтың толықтығы есептеуге болатын болса, онда ол ко-есептеуге болатын жиынтық деп аталады. Басқаша айтқанда, жиынтық ко-есептеуге болатын болады, егер және тек қана ол арифметикалық иерархия деңгейінде болса. Ко-есептеуге болатын жиынтықтардың күрделілік класы co RE деп белгіленеді. A жиынтығы есептеуге болатын болады, егер және тек қана A және A-ның толықтығы екеуі де есептеуге болатын болса. Кейбір есептеуге болатын жиынтықтардың жұптары тиімді түрде ажыратылады, ал кейбіреулері ажыратылмайды.
If A and B are computably enumerable sets then A ∩ B, A ∪ B and A × B (with the ordered pair of natural numbers mapped to a single natural number with the Cantor pairing function) are computably enumerable sets. The preimage of a computably enumerable set under a partial computable function is a computably enumerable set. A set is called co computably enumerable or co c. e. if its complement is computably enumerable. Equivalently, a set is co r. e. if and only if it is at level of the arithmetical hierarchy. The complexity class of co computably enumerable sets is denoted co RE. A set A is computable if and only if both A and the complement of A are computably enumerable. Some pairs of computably enumerable sets are effectively separable and some are not.
Ескертпелер
Church–Turing тезисіне сәйкес, кез келген тиімді есептелетін функция Тьюринг машинасымен есептеледі, демек S жиыны есептеуге болатын жиын болып табылады, егер және тек қана S жиынының тізімін беретін алгоритм болса. Дегенмен, бұл ресми анықтама ретінде қабылдана алмайды, себебі Church–Turing тезисі ресми аксиома емес, бұл бейресми болжам. Қазіргі заманғы мәтіндерде есептеуге болатын жиынды толық есептелмелі функцияның мәндер жиыны емес, ішінара функцияның анықталу облысы ретінде қарастыру жиі кездеседі. Мұндай таңдаудың себебі – жалпыланған рекурсиялық теорияларда, мысалы α-рекурсиялық теориясында, анықталу облысына сәйкес келетін анықтаманың көбірек табиғи екендігі анықталды. Басқа мәтіндерде жиынды тізімдеу арқылы анықтама беріледі, бұл есептеуге болатын жиындар үшін эквивалентті.
According to the Church–Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is computably enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom. The definition of a computably enumerable set as the domain of a partial function, rather than the range of a total computable function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as α recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for computably enumerable sets.