Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Անլուծելիության աստիճաններ և միթոտիկություն` ըստ թույլ (T- և wtt-) և աղյուսակային հանգեցումների

Մոկացյան, Արսեն Հակոբի (2012) Անլուծելիության աստիճաններ և միթոտիկություն` ըստ թույլ (T- և wtt-) և աղյուսակային հանգեցումների. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (391Kb) | Preview

    Abstract

    Первым исследованием в области митотических разбиений рекурсивно перечислимых множеств явилась работа А.Лахлана . Он доказал существование рекурсивно перечислимого немитотического множества. Систематическое исследование этого понятия произвел Р. Ладнер. Он в частности доказал идентичность этого понятия и понятия автосводимости (введенного Б.А. Трахтенбротом ). Р. Ладнер доказал существование всецело митотической рекурсивно перечис¬лимой степени. Р. Ладнер доказал также существование полного немитотического множества. Затем Р. Доуни и Т. Сламан произвели масштабное исследование всецело митотических степеней. Ими было доказано существование низкой нерекурсивной всецело митотической степени, а также существование высокой всецело митотической степени. Р. Доуни и Т. Сламан5 доказали также, что существует степень а такая, что для каждой степени Ь такой, что 0 < Ь < а степень Ь содержит немитотическое рекур¬сивно перечислимое множество. М. Инграссия доказал, что степени, содержащие немитотические рекурсивно перечислимые множества, плотны в Я. Исследование митотичности было успешно продолжено Е.Гриффитсом . Важные исследования, касающиеся д степеней, были произведены Л. Сассо. В частности, им было доказано, что любая тотальная д -степень имеет минимальное покрытие. Существенные результаты в этой области были получены Д. Скордевым и В.Поляковым. Обзор некоторых результатов, касающихся частичных степеней, можно найти в книге В.Полякова, М.Розинаса разработанных Колмогоровым . Он же доказал существование асимптотически оптимальных частично рекурсивных функций. Фундаментальные результаты в этой области получены Г.Б. Маранджяном13,14, М.И. Кановичем. Աշխատանքը նվիրված է ռեկուրսիվորեն թվարկելի բազմությունների' ըստ տարբեր տիպի հանգեցումների միթոտիկ տրոհման հնարավորությունների հետազոտմանը: Մասնավորապես, ապացուցվել է այնպիսի բազմությունների գոյությունը, որոնք համատեղում են T -միթոտիկությունը և ոչ- wtt -միթոտիկությունը, նաև այն բազմությունների գոյությունը, որոնք համատեղում են wtt -միթոտիկությունը և ոչ- tt -միթոտիկությունը, և վերջապես այնպիսինների գոյությունը, որոնք համատեղում են tt -միթոտիկությունը և ոչ- btt -միթոտիկությունը: Հետազոտվել է վերոհիշյալ տիպի բազմություններ պարունակող T -աստիճանների տեղաբաշխումը ռեկուրսիվորեն թվարկելի T -աստիճանների կիսացանցում: Սահմանում. Ռեկուրսիվորեն թվարկելի a աստիճանը անվանվում է միակցված (contiguous), եթե a -ին պատկանող A, B ռեկուրսիվորեն թվարկելի բազմությունների կամայական զույգի համար տեղի ունի A = wtt B: Միակցված աստիճանի սահմանումից հետևում է, որ միակցված աստիճանները չեն պարունակում T-միթոտիկ բազմություններ, որոնք wtt-միթոտիկ չեն: Ատենախոսության մեջ պացուցված է T-միթոտիկ, բայց ոչ-wtt-միթոտիկ բազմություն պարունակող T-աստիճանների խտությունը ռեկուրսիվորեն թվարկելի աստիճանների կիսացանցում: Ատենախոսության մեջ ապացուցված է այնպիսի ցածր ռեկուրսիվորեն թվարկելի u աստիճանի գոյությունը, որ եթե v-ն այնպիսի ռեկուրսիվորեն թվարկելի աստիճան է, որ u <v, ապա v-ն պարունակում է T-միթոտիկ, բայց ^-wtt-միթոտիկ բազմություն: Ուսումնասիրվել են նաև ը -աստիճանների կառուցվածքին վերաբերող հարցեր: Ռելյատիվիզացվել են բարդությունները ըստ Կոլմոգորովի և հետա¬զոտվել են նրանց հատկությունները: Ց(փ,W,c) o (Vxy)(թ (x) = y ^ (3 z)(փ(z) = y & l(z) < l(x) + c)), Լ1(Փ) o (3c) Q(փ,թ ,c) , Լշ(փ W) o Լւ(փ ,թ) & ^ Լիթ ,փ), Որտեղ փ, թ ' փոփոխականներ են, որոնց թույլատրելի արժեքներն են միտեղանի մասնակի ռեկեւրսիվ ֆունկցիաները, իսկ X, }>, 2, c ' փոփոխականներ են, որոնց թույլատրելի արժեքներն են բնական թվերը: A splitting of recursively enumerable set A is a pair A1, A2 of disjoin recursively enumerable sets such that A1 U A2 = A. Theorems about splitting have played an important role in recursion theory. The maim reason for this is that a splitting of A is a decomposition of A in both the lattice of recursively enumerable sets and in the uppersemilattice of recursively enumerable degrees (since A1 <T A, A2 <T A and A <T A1 ® ^2). Thus splitting theorems have used to obtain results about the structure of abovementioned lattice, of the structure of abovementioned uppersemilattice and the relationship between the two structures. Furthermore, the questions about splittings often generated important technical development in recursion theory. The earliest theorem is due to Friedberg (Friedberg’s Splitting theorem). Definition. An recursively enumerable set A is mitotic if there is a splitting A1, A2 of A such, that A1 =T A2 =T A . The definitions of wtt-, tt-, btt-mitoticities are similar to abovementioned mitoticity. A.Lachlan was the first, to show, that not all recursively sets are mitotic investigation of mitotic, but the first systematic investigation of mitotic sets was by R. Ladner . The first basic result reduces mitoticity to autoreduciblity, that is, a recursively enumerable set A is mitotic, if and only if A is auto reducible. Definition. An recursively enumerable set autoreducible if there is a functional O such that for every x, O( A U {x}) = A( x). An recursively enumerable degree a is contiguous, if for every pair A, B of recursively enumerable sets in a, A =wtt B. Note that contiguous degree does not contain T-mitotic but non-wtt- mitotic sets. The possibilities of mitotic splitting for some sets with respect to different reducibilities are investigated in this thesis.

    Item Type: Thesis (PhD)
    Additional Information: Անլուծելիության աստիճաններ և միթոտիկություն` ըստ թույլ (T- և wtt-) և աղյուսակային հանգեցումների: Unsolvability degrees and mitoticity with respect to weak (T- and wtt-) and truth table reducibilities.
    Uncontrolled Keywords: Մոկացյան Արսեն Հակոբի, Mokatsian Arsen
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 13 Mar 2017 13:29
    Last Modified: 13 Mar 2017 13:29
    URI: http://etd.asj-oa.am/id/eprint/4266

    Actions (login required)

    View Item