Кіріспе
Есептеуге қабілеттілік теориясындағы теорема, Эмиль Посттың есімімен аталатын Пост теоремасы, арифметикалық иерархия мен Тьюринг дәрежелері арасындағы байланысты сипаттайды.
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Өмірбаян
Пост теоремасының тұжырымында анықталуға және рекурсия теориясына қатысты бірнеше ұғымдар қолданылады. Бұл бөлімде осы ұғымдардың қысқаша шолуы берілген, олар тиісті мақалаларда егжей-тегжейлі қарастырылған. Арифметикалық иерархия Пеано арифметикасының тілінде анықталатын натурал сандардың белгілі бір жиындарын жіктейді. Формула, егер ол пренекс қалыпты түріндегі (барлық кванторлар басында) экзистенциалдық мәлімдеме болса, онда экзистенциалдық және жалпы кванторлардың арасында тек шектелген кванторлары бар формулаға қолданылатын кванторлардың саны m рет ауысады. Peano арифметикасының тіліндегі формула, егер ол тек шектелген кванторларды қамтитын болса және Q егер m жұп болса, ал егер m тақ болса, онда формуласы болып табылады. Натурал сандар жиыны, егер ол формуласымен анықталса, яғни әрбір сан жиынында тек және ғана орындалса, онда анықталатын болады деп айтылады. Егер жиын болса, онда ол кез келген үшін болады, бірақ әрбір m үшін болмайтын жиын бар екені белгілі. Осылайша, жиынды анықтау үшін қажетті кванторлардың ауысу саны жиынның күрделілігін көрсетеді. Пост теоремасы салыстырмалы арифметикалық иерархияны, сондай-ақ жаңа ғана анықталған салыстырмалы емес иерархияны пайдаланады. жиыны, егер жиынына қатысты оракул болса, деп жазылады, егер жиыны жиынындағы мүшелікке қатысты предикатты қамтитын кеңейтілген тілдегі формуласымен анықталса. Арифметикалық иерархия натурал сандар жиындарының анықталуын өлшейтін болса, Тьюринг дәрежелері натурал сандар жиындарының есептелмейтін деңгейін өлшейді. жиыны, егер жиынына қатысты Тьюринг азайтылатын болса, деп жазылады, егер жиыны үшін оракул берілгенде функциясын есептейтін оракул Тьюринг машинасы болса. жиынының Тьюринг секіруі – бұл жиынына қатысты тоқтау мәселесінің бір түрі. жиыны берілген болса, Тьюринг секіруі – бұл оракулмен жұмыс істегенде кірісінде тоқтайтын оракул Тьюринг машиналарынң индекстерінің жиыны. Пост теоремасы шекті қайталамалы Тьюринг секірулерін қолданады. Кез келген натурал сандар жиыны үшін жазуы жиынының рет қайталамалы Тьюринг секіруін көрсетеді. Осылайша дегеніміз ал, – жиынының Тьюринг секіруі.
where contains only bounded quantifiers and Q is if m is even and if m is odd. A set of natural numbers is said to be if it is definable by a formula, that is, if there is a formula such that each number is in if and only if holds. It is known that if a set is then it is for any , but for each m there is a set that is not Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set. Post's theorem uses the relativized arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set of natural numbers is said to be relative to a set , written , if is definable by a formula in an extended language that includes a predicate for membership in
While the arithmetical hierarchy measures definability of sets of natural numbers, Turing degrees measure the level of uncomputability of sets of natural numbers. A set is said to be Turing reducible to a set , written , if there is an oracle Turing machine that, given an oracle for , computes the characteristic function of The Turing jump of a set is a form of the Halting problem relative to Given a set , the Turing jump is the set of indices of oracle Turing machines that halt on input when run with oracle It is known that every set is Turing reducible to its Turing jump, but the Turing jump of a set is never Turing reducible to the original set. Post's theorem uses finitely iterated Turing jumps. For any set of natural numbers, the notation indicates the –fold iterated Turing jump of Thus is just , and is the Turing jump of .
Бірінші реттік арифметикада Тьюринг машиналарын формализациялау
Тьюринг машинасының кіріспен жұмыс істеуін бірінші реттік арифметикада логикалық түрде формалдауға болады. Мысалы, таспа конфигурациясы, машинаның күйі және қадамдардан кейін таспа бойымен орналасуы үшін біз , , және символдарды қолдана аламыз. Машинаның өту жүйесі арасындағы қатынасты анықтайды; олардың бастапқы мәндері ( кіріс үшін) – сәйкесінше кіріс, бастапқы күй және нөл. Машина тоқтайды, егер және тек қана тоқтау күйі болатын сан болса. Нақты қатынас Тьюринг машинасы ұғымының нақты іске асырылуына байланысты (мысалы, олардың әліпбиі, таспа бойымен қозғалудың рұқсат етілген режимі және т.б.). Егер машина уақытпен тоқтаса, онда арасындағы қатынас тек жоғарыдан шектелген болатын үшін ғана орындалуы керек. Осылайша, бірінші реттік арифметикада шектелмеген кванторлары жоқ формула бар, егер және тек қана орындалса, онда машина кіріспен уақыттың ішінде тоқтайды.
Thus there is a formula in first order arithmetic with no unbounded quantifiers, such that halts on input at time at most if and only if is satisfied.
Қайталап саналатын жиынтықтар
Тьюринг машинасымен рекурсивті санауға болатын жиынтық болсын. Онда, әрбір x ∈ A үшін, x-ті кіріс ретінде алғанда тоқтайтын Тьюринг машинасы бар. Бұл жоғарыда келтірілген бірінші реттік арифметикалық формуламен формальдастырылуы мүмкін. А жиынтығының мүшелері келесі формуламен қанағаттандырылатын сандар болып табылады:
Бұл формула Σ₀-да. Сондықтан, А жиынтығы Σ₀-да. Осылайша, кез келген рекурсивті саналатын жиынтық Σ₀-да болады.
Керісі де дұрыс: кез келген φ формуласы k экзистенциалды кванторлармен Σ₀-да болса, біз натурал сандардың k-тіктерін санап шыға аламыз және формула қанағаттандырылғанша олардың барлығын қарастыратын Тьюринг машинасына жүгіртеміз. Бұл Тьюринг машинасы φ-ні қанағаттандыратын натурал сандар жиынтығында тоқтайды, демек оның сәйкес жиынтығын санайды.
Тьюрингтің жоғары секіруі
Жалпырақ айтқанда, егер кез келген жиын оракул машинасы арқылы санамалы болса, онда ол жиын ішінде болады. Оракул машинасы үшін, оракулмен жабдықталған болса, онда ол жиын ішінде болады.
-ның алдыңғы Тюринг секірісімен бірдей болғандықтан, оны (жоғарыдағы -мен жасағанымыздай) осылай құруға болады, сонда ол ішінде болады. Жаңадан алынғаннан кейін, жаңа жиын ішінде болады.
Индукция бойынша, оракул машинасымен оракул үшін санамалы болатын кез келген жиын ішінде болады.
Кері бағытта да индукция арқылы дәлелдеуге болады: егер -дегі барлық формула оракул машинасымен оракул үшін санамалы болса, демек.
Енді, -дегі формуланы қарастырайық, онда экзистенциалдық сандықтардан кейін жалпылама сандықтар келеді және т.б. Балама түрінде, -да > экзистенциалдық сандықтардан кейін -дегі формуланың жоғарысы келеді; соңғы формула оракул машинасымен оракул үшін санамалы және осылайша оракулмен бірден тексеріледі.
Осылайша, біз табиғи сандардың топтамаларын санап, оракул машинасымен оракул үшін олардың барлығын формулаға қанағаттанғанша ашамыз. Бұл оракул машинасы нақты қанағаттандыратын табиғи сандар жиынында тоқтап, осылайша оның сәйкес жиынын санап шығарады.
Since is the same as for the previous Turing jump, it can be constructed (as we have just done with above) so that in After moving to prenex formal form the new is in
By induction, every set that is recursively enumerable by an oracle machine with an oracle for , is in
The other direction can be proven by induction as well: Suppose every formula in can be enumerated by an oracle machine with an oracle for
Now Suppose is a formula in with existential quantifiers followed by universal quantifiers etc. Equivalently, has > existential quantifiers followed by a negation of a formula in ; the latter formula can be enumerated by an oracle machine with an oracle for and can thus be checked immediately by an oracle for
We may thus enumerate the –tuples of natural numbers and run an oracle machine with an oracle for that goes through all of them until it finds a satisfaction for the formula. This oracle machine halts on precisely the set of natural numbers satisfying , and thus enumerates its corresponding set.