K-тривиалды жиынтық - Википедия - K-trivial set

Бұл мақала болып табылады жетім, басқа мақалалар сияқты емес оған сілтеме. өтінемін сілтемелерді енгізу осы параққа қатысты мақалалар; көріңіз Сілтеме құралын табыңыз ұсыныстар үшін. (Наурыз 2014)

Жылы математика, натурал сандар жиыны а деп аталады K-тривиалды жиынтық егер ол бастапқы сегменттер екілік жолдар ретінде қарастыруға оңай: префиксі жоқ Колмогоровтың күрделілігі а-ға жақын, мүмкіндігінше төмен есептелетін жинақ. Соловай 1975 жылы жинақ есептелмейтін K-тривиальды бола алатындығын дәлелдеді.

The Шнорр-Левин теоремасы кездейсоқ жиынтықтардың бастапқы сегменттің күрделілігі жоғары дейді. Осылайша, K-тривиалдар кездейсоқтықтан алыс. Сондықтан бұл жиынтықтар облысында зерттеледі алгоритмдік кездейсоқтық, бұл кіші алаң Есептеу теориясы және байланысты алгоритмдік ақпарат теориясы жылы Информатика.

Сонымен бірге, K-тривиальды жиынтықтар есептеуге жақын. Мысалы, олардың барлығы суперлоу, яғни кімдікі Тюрингтен секіру есептелінеді Мәселені тоқтату, және а Тюринг идеалы, яғни астында жабылған жиындар класы Тьюрингке қосылыңыз және астына қарай жабылды Тюрингтің төмендеуі.

Анықтама

K префиксі жоқ болсын Колмогоров күрделілігі, яғни x жолы берілгенде, K (x) а жолының астына кіріс жолының ең аз ұзындығын шығарады префиксі жоқ әмбебап машина. Мұндай машина интуитивті түрде басқа жарамды бағдарламаның дұрыс кеңеюі ретінде ешқандай жарамды бағдарлама алуға болмайтын қасиеті бар әмбебап бағдарламалау тілін ұсынады. K туралы көбірек мәлімет алу үшін, мысалы, қараңыз. Чайтиннің тұрақтысы.

Біз жиынтықтың А жиынтығын айтамыз натурал сандар тұрақты b constant ℕ арқылы K-тривиальды болады, егер

${ displaystyle forall nK (A upharpoonright n) leq K (n) + b}$.

Жиын K-тривиалды, егер ол қандай да бір тұрақты арқылы K-тривиалды болса.^[1][2]

Қысқаша тарихы және дамуы

К-тривиальдылықтың дамуының алғашқы күндерінде К-тривиальды жиынтықтарды бөлуге және есептелетін жиынтықтар.

Чайтин 1976 жылғы мақаласында ^[3] b ∈ℕ бар болатын негізінен зерттелген жиынтықтар

${ displaystyle forall nC (A upharpoonright n) leq C (n) + b}$

мұндағы C жазықты білдіреді Колмогоровтың күрделілігі. Бұл жиындар C-тривиалды жиындар ретінде белгілі. Чайтин олардың есептелетін жиынтықтармен сәйкес келетіндігін көрсетті. Ол сондай-ақ K-тривиалдарының есептелетіндігін көрсетті мәселені тоқтату. Жиындардың бұл класы, әдетте, ретінде белгілі ${ displaystyle Delta _ {2} ^ {0}}$ кіреді арифметикалық иерархия.

Роберт М. Соловай бірінші болып есептелмейтін К-тривиальды жиынтық құрды, ал есептеуге болатын А-ны салуға тырысты. Калуде, Колес ^[4] және басқа жарияланбаған К-тривиальды Куммер және К жиынтығы үшін кіші кіші Мучник салған.

Дамулар 1999–2008 жж

Есептеу теориясы тұрғысынан шығын функциясы есептелетін функция болып табылады

${ displaystyle c: mathbb {N} times mathbb {N} to mathbb {Q} ^ { geq 0}.}$

Есептелетін жуықтау үшін ${ displaystyle langle A_ {s} rangle}$ туралы ${ displaystyle Delta _ {2} ^ {0}}$ орнатылды A, мұндай функция шығындарды өлшейді c(n,с) s кезеңінде A (n) жуықтауын өзгерту. Бірінші шығындар функциясы құрылыс Кучера мен Тервейнге байланысты болды.^[5] Олар а санауға болатын Мартин-Лёф-кездейсоқтық үшін төмен, бірақ есептелмейтін жиын. Олардың шығындар функциясы адаптивті болды, өйткені шығындар функциясын анықтау $ -ның есептелетін жақындауына байланысты ${ displaystyle Delta _ {2} ^ {0}}$ жинақ салынуда.

К-тривиалдың өзіндік құны функциясы санауға болатын есептелмейтін жиынтық алғаш рет Дауни және басқаларда пайда болды.^[6]

Біз а ${ displaystyle Delta _ {2} ^ {0}}$ орнатылды A шығындар функциясына бағынады c егер есептелетін A жуықтауы болса, ${ displaystyle langle A_ {s}: s in omega rangle}$${ displaystyle S = Sigma _ {x, s} c (x, s) [x$

K-тривиальды жиынтықтар сипатталады^[7] бағыну арқылы Стандартты шығындар функциясы, арқылы анықталады

${ displaystyle c_ {K} (x, s) = Sigma _ {x$ қайда ${ displaystyle K_ {s} (x) = min {| sigma |: mathbb {U} _ {s} ( sigma) = x }}$

және ${ displaystyle mathbb {U} _ {s}}$ болып табылады с- тіркелген әмбебап префиксі жоқ машинаның есептелген жуықтауының үшінші сатысы ${ displaystyle mathbb {U}}$.

Есептелмейтін К-тривиальды жиынтықтың эскизі

Іс жүзінде жиынтықты жасауға болады жедел. Идеясы - қарапайым қарапайымдылықтың жедел талаптарын қанағаттандыру,

${ displaystyle PS_ {e}: | W_ {e} | = infty Rightarrow бар s бар x [x in W_ {e, s} кері сызығы W_ {e, s-1} wedge x in A_ {s}]}$

сонымен қатар шығындарды аз ұстау үшін. Бізге қанағаттандыру үшін шығындар функциясы қажет шекті шарт

${ displaystyle lim _ {x} sup _ {s> x} c (x, s) = 0}$

дәлірек айтқанда, х-тің шығын кезеңдеріндегі супремум х-тің өсуіне қарай 0-ге ауысады. Мысалы, стандартты шығын функциясы осы қасиетке ие. Құрылыс сандарды қоймас бұрын құны төмен болғанша күтеді ${ displaystyle A}$ жедел талаптарға сай болу. Біз есептелетін санауды анықтаймыз ${ displaystyle langle A_ {s}: s in omega rangle}$ осындай

${ displaystyle A_ {0} = emptyset}$. Кезеңде с> 0, әрқайсысы үшін e < с, егер ${ displaystyle PS_ {e}}$ әлі кездескен жоқ және бар х ≥ 2e осындай ${ displaystyle x in W_ {e, s} backslash W_ {e, s-1}}$ және ${ displaystyle c (x, s) leq 2 ^ {- e}}$, содан кейін біз қойдық х ішіне ${ displaystyle A_ {s}}$ және бұл туралы мәлімдеңіз ${ displaystyle PS_ {e}}$ кездеседі. Құрылыстың аяқталуы.

Құрылыс жұмыстарының жүргізіліп жатқанын тексеру үшін алдымен ескеріңіз A шығын функциясына бағынады, өйткені көп дегенде бір сан енгізіледі A әрбір талап үшін. Қосынды S сондықтан ең көп

${ displaystyle Sigma _ {e} 2 ^ {- e} < infty.}$

Екіншіден, әрбір талап орындалады: егер ${ displaystyle W_ {e}}$ шексіз, өйткені шығын функциясы шекті шартты қанағаттандырады, кейбір сан ақыр соңында талапты қанағаттандыру үшін А санына енеді.

Эквивалентті сипаттамалар

K-тривиалдылық жиынтық есептелуге жақын деп, кейбір есептеудің төмендік түсініктерімен сәйкес келеді. Келесі түсініктер жиынтықтардың бірдей класын алады.^[7]

Үшін иесіз Қ

Біз мұны айтамыз A төмен Қ егер бар болса б ℕ ℕ осылай

${ displaystyle forall nK ^ {A} (n) + b geq K (n).}$

Мұнда ${ displaystyle K ^ {A}}$ префикссіз Колмогоровтың күрделілігі ораклге қатысты ${ displaystyle A}$.

Мартин-Лёф-кездейсоқтықтың иесі

Мартин-Лёф-кездейсоқтық үшін төмен^[8] егер Z болса Мартин-Лёф кездейсоқ, ол қазірдің өзінде Мартин-Лёф кездейсоқ қатысты A.

Мартин-Лёф-кездейсоқтықтың негізі

A егер Мартин-Лёф-кездейсоқтық үшін негіз болса A болып табылады Тьюринг төмендейді дейін З кейбір жиынтығы үшін З Бұл Мартин-Лёф кездейсоқ қатысты A.

^[7]

К-тривиалдылықтың баламалы сипаттамалары зерттелді, мысалы:

1. Әлсіз-2-кездейсоқтықтың иесі;
2. Сол жақ-айырмашылықтың иесі. реал (бұл жерде кездейсоқтық туралы айтылмайды).

2008 жылдан кейінгі даму

2009 жылдан бастап талдау тұжырымдамалары сахнаға шықты. Бұл кейбір белгілі мәселелерді шешуге көмектесті.

Біреуі Y жиынтығы оң тығыздық нүктесі болып табылады, егер Y бар барлық тиімді жабық класс Y-да оң төменгі лебесг тығыздығына ие болса, Биенвену, Хольцль, Миллер және Ньес^[9] ML-кездейсоқ Тьюрингтің толық емес екендігін көрсетті, егер ол оң тығыздық нүктесі болса. Дэй және Миллер^[10] мұны ML-купинг мәселесіне оң жауап беру үшін пайдаланды:^[11] A - Мартин-Лёф кез-келген кездейсоқ Z жиынтығы үшін K-тривиальды iff, сондықтан A⊕Z есептейтін болады мәселені тоқтату, қазірдің өзінде Z өзі есептейді мәселені тоқтату.

Біреуі Y жиынтығы тығыздық-бір нүкте, егер Y бар барлық жабық класс Y-де Лебегдің тығыздығы 1-ге тең болса, тығыздық емес кез-келген Мартин-Лёф кездейсоқ жиыны - бір нүкте Биенвену орнатқан әрбір К тривиальды жиынды есептейді дейді. .^[12] Дэй мен Миллер Мартин-Лёф кездейсоқ жиынтығы бар екенін көрсетті, ол оң тығыздық нүктесі, бірақ тығыздық бір нүкте емес. Осылайша, кез-келген К-тривиальды жиынды есептейтін толық емес осындай Мартин-Лёф кездейсоқ жиыны бар. Бұл оң жауап берді мәселені қамту алдымен Стефан сұрады, содан кейін Миллер мен Нис жариялады.^[13] Түйіндеме үшін Л.Биенвену, А.Дэй, Н.Гринберг, А.Куцера, Дж.Миллер, А.Нис және Д.Турецкийді қараңыз.^[14]

К-тривиалдылықтың нұсқалары зерттелді:

• Шнордың тривиальды жиынтығы онда машиналар есептелетін өлшеммен доменге ие.
• қадағаланатын жиынтықтардан қатты секіру, K-тривиалитет ішіндегі жиынтықтардың төмен қасиеті.

Әдебиеттер тізімі