Тьюринг дәрежесі: Есептелмейтін мәселелердің өлшемі

Кіріспе

Ерілмеушіліктің өлшемі Компьютерлік ғылым мен математикалық логикада Тьюринг дәрежесі (Алан Тьюрингтің құрметіне аталған) немесе табиғи сандар жиынының ерілмеушілік дәрежесі, жиынның алгоритмдік шешілмейтін деңгейін анықтайды.

Шолу

Тьюринг дәрежесінің түсінігі есептеу теориясындағы негізгі ұғым болып табылады, онда табиғи сандар жиындары көбінесе шешімдік есептер ретінде қарастырылады. Жиынның Тьюринг дәрежесі – бұл жиынмен байланысты шешімдік есепті шешудің қиындығын өлшейтін шама, яғни кез келген санның берілген жиынға жататынын анықтау. Егер екі жиынның шешілмейтін деңгейі бірдей болса, онда олар Тьюрингтік эквивалентті болып есептеледі; әр Тьюринг дәрежесі – Тьюрингтік эквивалентті жиындардың жиынтығы, сондықтан екі жиын Тьюрингтік эквивалентті болмаған жағдайда ғана әртүрлі Тьюринг дәрежесінде болады. Сонымен қатар, Тьюринг дәрежелері ішінара реттелген, яғни егер X жиынының Тьюринг дәрежесі Y жиынының Тьюринг дәрежесінен төмен болса, онда Y жиынындағы сандардың бар-жоғын дұрыс анықтайтын (мүмкін есептелмейтін) кез келген процедураны X жиынындағы сандарды дұрыс анықтайтын процедураға тиімді түрде түрлендіруге болады. Осы тұрғыдан алғанда, жиынның Тьюринг дәрежесі оның алгоритмдік шешілмейтін деңгейіне сәйкес келеді. Тьюринг дәрежесі енгізілді және одан бері көптеген маңызды нәтижелер дәлелденді. Бұл саланың көптеген дәлелдемелері басымдық әдісі деп аталатын дәлелдеу техникасын пайдаланады.

Тьюринг дәрежесінің негізгі қасиеттері

Әрбір Тьюринг дәрежесі санауға болатын шексіз, яғни, ол дәл жиынтықтарды қамтиды. Ерекше Тьюринг дәрежелері бар. Кез келген a дәрежесі үшін a < a′ қатаң теңсіздігі орындалады. Кез келген a дәрежесі үшін a-дан төменгі дәрежелер жиыны санаулы болады. a-дан жоғары дәрежелер жиынының саны бар.

Тьюринг дәрежесінің құрылымы

Тьюринг дәрежесінің құрылымын зерттеуге көптеген еңбек жұмсалды. Төмендегі шолуда белгілі нәтижелердің бір бөлігі ғана тізілген. Зерттеулерден шығаратын жалпы қорытынды – Тьюринг дәрежесінің құрылымы өте күрделі.

Тапсырма қасиеттері

Минималды дәрежелер бар. Егер a нөлден өзгеше болса және 0 мен a арасында дәреже болмаса, a дәрежесі минималды болып есептеледі. Осылайша, дәрежелер арасындағы реттік қатынас тығыз реттік емес. Тьюринг дәрежелері &leq;T бойынша сызықтық түрде реттелмейді.

Шындығында, нөлден өзгеше кез келген a дәрежесі үшін, a-мен салыстырылмастан, b дәрежесі табылады. Бір-бірімен салыстырылмастан Тьюринг дәрежелерінің жиынтығы бар. Ең үлкен төменгі шегі жоқ дәрежелер жұптары бар. Сондықтан, бұл тор емес. Кез келген саналатын ішінара реттелген жиынды Тьюринг дәрежелеріне ендіруге болады. Тьюринг дәрежелерінің a1, a2, ... түріндегі шексіз өсуімен берілген тізбегінің ең кіші жоғарғы шегі болмайды, бірақ оның әрқашан ∀e (e<c ∧ e<d ⇔ ∃i e≤ai) шартын қанағаттандыратын дәл c, d жұбы болады, демек, оның (бірегей емес) ең кіші жоғарғы шегі бар. Құрылыстылық аксиомасын қабылдасақ, дәрежелердің тәртіп түрінің максималды тізбегі бар екенін көрсетуге болады.

Секіруге қатысы бар қасиеттер

Кез келген a дәрежесі үшін a мен a′ арасында қатаң түрде a мен a′-ның арасындағы дәреже бар. Шындығында, a мен a′ арасында жұп-жұп салыстыруға келмейтін саналатын дәрежелер отбасы бар. Секундыра инверсиясы: a дәрежесі b′ түрінде болады, егер және ғана егер 0′ ≤ a болса. Кез келген a дәрежесі үшін a < b және b′ = a′ болатын b дәрежесі бар; мұндай b дәрежесі a-ға қатысты төмен деп аталады. Әр i үшін a′i+1 ≤ ai болатын шексіз aі дәрежелері тізбегі бар. Пост теоремасы арифметикалық иерархия мен бос жиынның шекті қайталамалы Тьюринг секірулері арасындағы тығыз сәйкестікті белгілейді.

Логикалық қасиеттері

тіліндегі 1=〈 ≤, = 〉 немесе 1=〈 ≤, ′, = 〉 бірінші реттік теориясы нақты екінші реттік арифметика теориясына көпке бірдей эквивалентті екенін көрсетті. Бұл құрылымының өте күрделі екенін көрсетеді. секіру операторының 1=〈 ≤, = 〉 тіліндегі бірінші реттік құрылымында анықталатынын көрсетті.

Қайта саналатын Тьюринг дәрежесі

Егер дәреже рекурсивті түрде саналатын жиынтықты қамтыса, онда ол рекурсивті түрде саналатын (r.e.) немесе есептеулі түрде саналатын (c.e.) деп аталады. Кез келген r.e. дәрежесі 0′-дан төмен, бірақ 0′-дан төменгі барлық дәреже r.e. емес. Алайда, жиынтық көпке-бір азайту арқылы 0′-ға келтірілсе, ол r.e. болады. : r.e. дәрежелері тығыз; кез келген екі r.e. дәрежесінің арасында үшінші r.e. дәрежесі бар. және: r.e. дәрежелерінде ең үлкен төменгі шегі жоқ екі r.e. дәрежесі бар. және: ең үлкен төменгі шегі 0 болатын нөлден өзгеше r.e. дәрежелер жұбы бар. : ең үлкен төменгі шегі 0 және ең кіші жоғарғы шегі 0′ болатын r.e. дәрежелер жұбы жоқ. Бұл нәтиже бейресми түрде «алмас емес теоремасы» деп аталады. : Кез келген шекті үлестірімді тор r.e. дәрежелеріне енгізілуі мүмкін. Шындығында, саналатын атомсыз Буль алгебрасы жоғары және төменгі шектерді сақтайтын тәсілмен енгізілуі мүмкін. : Барлық шекті торларды r.e. дәрежелеріне ендіру мүмкін емес (жоғары және төменгі шектерді сақтайтын енгізу арқылы). Оң жақта көрсетілген мысал осыны көрсетеді. Л.А. Харрингтон және Т.А. Сламан (қараңыз): r.e. дәрежелерінің 〈0, ≤, =〉 тіліндегі бірінші реттік теориясы нақты бірінші реттік арифметика теориясына көптен-бір сәйкес келеді. Сонымен қатар, Шёнфилдтің шектеу леммасы бар: A жиыны егер оның сипаттамалық функциясына «рекурсивті жуықтама» болса, онда оны қанағаттандырады: g функциясы жеткілікті үлкен s үшін. A жиыны n r.e. деп аталады, егер функциялар отбасы болса: As жиыны A-ның рекурсивті жуықтамасы: кейбір t үшін, кез келген s≥t үшін As(x) = A(x) болады, атап айтқанда A-ны оның сипаттамалық функциясымен теңестіру. (Бұл шартты алып тастау A-ның «әлсіз n r.e.» екенін анықтайды.) As «n сынақ предикаты»: барлық x үшін A0(x) = 0 және cardinality ≤n. n r.e. дәрежелерінің қасиеттері: n r.e. дәрежелі жиынтықтар класы (n+1) r.e. дәрежелі жиынтықтар класының қатаң ішкі класы болып табылады. Барлық n>1 үшін екі (n+1) r.e. a, b дәрежесі бар, мұнда сегментінде n r.e. дәрежесі жоқ. және егер екі жиын да әлсіз n r.e. болса, онда олар (n+1) r.e. болады.

A degree is called recursively enumerable (r. e.) or computably enumerable (c. e.) if it contains a recursively enumerable set. Every r. e. degree is below 0′, but not every degree below 0′ is r. e However, a set is many one reducible to 0′ iff is r. e

: The r. e. degrees are dense; between any two r. e. degrees there is a third r. e. degree. and : There are two r. e. degrees with no greatest lower bound in the r. e. degrees. and : There is a pair of nonzero r. e. degrees whose greatest lower bound is 0.
: There is no pair of r. e. degrees whose greatest lower bound is 0 and whose least upper bound is 0′. This result is informally called the nondiamond theorem. : Every finite distributive lattice can be embedded into the r. e. degrees. In fact, the countable atomless Boolean algebra can be embedded in a manner that preserves suprema and infima. : Not all finite lattices can be embedded in the r. e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right. L. A. Harrington and T. A. Slaman (see ): The first order theory of the r. e. degrees in the language 〈 0, ≤, = 〉 is many one equivalent to the theory of true first order arithmetic. Additionally, there is Shoenfield's limit lemma, a set A satisfies iff there is a "recursive approximation" to its characteristic function: a function g such that for sufficiently large s,
A set A is called n r e. if there is a family of functions such that:
As is a recursive approximation of A: for some t, for any s&geq;t we have As(x) = A(x), in particular conflating A with its characteristic function. (Removing this condition yields a definition of A being "weakly n r. e.")
As is an "n trial predicate": for all x, A0(x)=0 and the cardinality of is &leq;n.

Properties of n r. e. degrees:
The class of sets of n r. e. degree is a strict subclass of the class of sets of (n+1) r. e. degree. For all n>1 there are two (n+1) r. e. degrees a, b with , such that the segment contains no n r. e. degrees. and are (n+1) r. e. iff both sets are weakly n r. e.

Пост проблемасы және басымдық беру әдісі

Эмиль Пост зерттеді r.e. Тьюринг дәрежесін және сұрады, 0 мен 0′ аралығында r.e. дәрежесі бар ма. Мұндай дәреже құру (немесе оның жоқ екенін көрсету) мәселесі Пост мәселесі ретінде белгілі болды. Бұл мәселені Фридберг пен Мухник 1950 жылдары тәуелсіз түрде шешті, олар осы аралық r.e. дәрежелердің бар екенін көрсетті (Фридберг–Мухник теоремасы). Олардың дәлелдерінің әрқайсысы r.e. дәрежелерін құрудың бірдей жаңа әдісін жасады, ол басымдық әдісі деп аталды. Басымдық әдісі қазір r.e. жиындары туралы нәтижелерді орнатудың негізгі техникасы болып табылады. r.e. жиынын құрудың басымдық әдісінің идеясы X-тің қанағаттандыруы тиіс талаптардың саналатын тізбесін тізімдеу болып табылады. Мысалы, 0 мен 0′ аралығындағы r.e. жиынын құру үшін X әрбір табиғи сан e үшін Ae және Be талаптарын қанағаттандыру жеткілікті, мұнда Ae индексі e бар оракул машинасы X-тен 0′ есептелмеуін талап етеді, ал Be индексі e бар (және оракулсыз) Тьюринг машинасы X-ті есептелмеуін талап етеді. Бұл талаптар басымдық ретімен орналастырылады, яғни талаптар мен табиғи сандардың нақты бірге орналасуы. Дәлел әрбір табиғи сан үшін бір кезеңмен индуктивті түрде жүреді; бұл кезеңдерді X жиыны саналатын уақыт қадамдары ретінде қарастыруға болады. Әрбір кезеңде сандар X-ке қосылуы мүмкін немесе (зақымданбаса) X-ке кіруіне мәңгілікке кедергі келтірілуі мүмкін, талаптарды қанағаттандыру үшін (яғни, X-тің барлық элементтері саналғаннан кейін оларды орындауға мәжбүрлеу). Кейде бір талапты қанағаттандыру үшін санды X-ке қосуға болады, бірақ бұл бұрын қанағаттандырылған талапты қанағаттандырылмаған (яғни, зақымдалған) қалпына келтіруі мүмкін. Талаптардың басымдық реті осы жағдайда қай талапты қанағаттандыру керектігін анықтау үшін қолданылады. Формальды түрде айтқанда, егер талап зақымдалса, онда ол барлық жоғары басымдықтағы талаптардың зақымдалуын тоқтатқаннан кейін зақымдалуын тоқтатады, бірақ барлық басымдық аргументтері осы қасиетке ие емес. Жалпы X жиынының r.e. екенін және барлық талаптарды қанағаттандыратынын дәлелдеу қажет. Басымдық аргументтерін r.e. жиындары туралы көптеген фактілерді дәлелдеу үшін қолдануға болады; қажетті нәтижені алу үшін қолданылатын талаптар мен оларды қанағаттандыру тәсілі мұқият таңдалуы керек. Мысалы, қарапайым (осылайша есептелмейтін r.e.) төмен X (төмен дегеніміз X′=0′) келесідей шексіз көп қадамда құрастырылуы мүмкін. n-ші қадамның басында Tn - біз 1-ді орналастырған ұяшықтар индекстерінің жиынымен сәйкес келетін шығыс (бинарлық) таспасы болсын (осылайша X=∪n Tn; T0=∅); және Pn(m) - m орнында 1 шығаруға болмайтын басымдық болсын; P0(m)=∞. n-ші қадамда, мүмкін болса (әйтпесе қадамда ештеңе жасамаңыз), ∀m Pn(m)≠i және Тьюринг машинасы i ∀m∈S\Tn Pn(m)≥i болатын STn кірісінде <n қадамда тоқтатын ең кішкентай i<n таңдаңыз. Кез келген (шекті) S таңдаңыз, Tn+1=S деп қойыңыз, және S-тегі машина i барған әрбір ұяшыққа Pn+1(m) = min(i, Pn(m)) деп қойыңыз, және барлық басымдықтарды >i ∞-ға қойыңыз, содан кейін S-те жоқ бір басымдық ∞ ұяшықты (кез келгені) i басымдығына қойыңыз. Негізінде, егер біз бұл басымдықтарды бұзбай жасай алсақ, машинаны тоқтатуға рұқсат етеміз, содан кейін машиналардың тоқтауын бұзбау үшін басымдықтарды орнатамыз; барлық басымдықтар ақырында тұрақты болады. X төмен екенін көрсету үшін, машина i X-те тоқтайды, егер ол кейбір Tn-де <n қадамда тоқтаса, және X-те тоқтайтын машиналар <i <n қадамда тоқтайды (рекурсия бойынша, бұл 0′-дан біркелкі есептеледі). X есептелмейді, өйткені әйтпесе Тьюринг машинасы Y-де тоқтай алады, егер Y\X бос болмаса, бұл құрылысқа қайшы келеді, өйткені X кез келген үлкен i үшін кейбір i басымдықты ұяшықтардан шығарып тастайды; және X қарапайым, өйткені әрбір i үшін i басымдықты ұяшықтар саны шекті.

Emil Post studied the r. e. Turing degrees and asked whether there is any r. e. degree strictly between 0 and 0′. The problem of constructing such a degree (or showing that none exist) became known as Post's problem. This problem was solved independently by Friedberg and Muchnik in the 1950s, who showed that these intermediate r. e. degrees do exist (Friedberg–Muchnik theorem). Their proofs each developed the same new method for constructing r. e. degrees, which came to be known as the priority method. The priority method is now the main technique for establishing results about r. e. sets. The idea of the priority method for constructing a r. e. set X is to list a countable sequence of requirements that X must satisfy. For example, to construct a r. e. set X between 0 and 0′ it is enough to satisfy the requirements Ae and Be for each natural number e, where Ae requires that the oracle machine with index e does not compute 0′ from X and Be requires that the Turing machine with index e (and no oracle) does not compute X. These requirements are put into a priority ordering, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set X is enumerated. At each stage, numbers may be put into X or forever (if not injured) prevented from entering X in an attempt to satisfy requirements (that is, force them to hold once all of X has been enumerated). Sometimes, a number can be enumerated into X to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be injured). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set X is r. e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r. e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result. For example, a simple (and hence noncomputable r. e.) low X (low means X′=0′) can be constructed in infinitely many stages as follows. At the start of stage n, let Tn be the output (binary) tape, identified with the set of cell indices where we placed 1 so far (so X=∪n Tn; T0=∅); and let Pn(m) be the priority for not outputting 1 at location m; P0(m)=∞. At stage n, if possible (otherwise do nothing in the stage), pick the least i<n such that ∀m Pn(m)≠i and Turing machine i halts in <n steps on some input S⊇Tn with ∀m∈S\Tn Pn(m)≥i. Choose any such (finite) S, set Tn+1=S, and for every cell m visited by machine i on S, set Pn+1(m) = min(i, Pn(m)), and set all priorities >i to ∞, and then set one priority ∞ cell (any will do) not in S to priority i. Essentially, we make machine i halt if we can do so without upsetting priorities <i, and then set priorities to prevent machines >i from disrupting the halt; all priorities are eventually constant. To see that X is low, machine i halts on X iff it halts in <n steps on some Tn such that machines <i that halt on X do so <n i steps (by recursion, this is uniformly computable from 0′). X is noncomputable since otherwise a Turing machine could halt on Y iff Y\X is nonempty, contradicting the construction since X excludes some priority i cells for arbitrarily large i; and X is simple because for each i the number of priority i cells is finite.