K-тривиальный набор

Тип множества в математике

В математике множество натуральных чисел называется K-тривиальным множеством , если его начальные сегменты, рассматриваемые как двоичные строки, легко описать: префиксная сложность Колмогорова настолько мала, насколько это возможно, близка к сложности вычислимого множества . В 1975 году Соловей доказал, что множество может быть K-тривиальным, не будучи вычислимым.

Теорема Шнорра–Левина утверждает, что случайные множества имеют высокую начальную сложность сегмента. Таким образом, K-тривиалы далеки от случайности. Вот почему эти множества изучаются в области алгоритмической случайности , которая является подразделом теории вычислимости и связана с алгоритмической теорией информации в информатике .

В то же время K-тривиальные множества близки к вычислимым. Например, все они являются супернизкими, т.е. множествами, скачок Тьюринга которых вычислим из проблемы остановки , и образуют идеал Тьюринга, т.е. класс множеств, замкнутых относительно объединения Тьюринга и замкнутых вниз относительно редукции Тьюринга .

Определение

Пусть K будет префиксной колмогоровской сложностью , т. е. для заданной строки x, K(x) выводит наименьшую длину входной строки на префиксной универсальной машине . Такая машина, интуитивно, представляет собой универсальный язык программирования со свойством, что никакая допустимая программа не может быть получена как надлежащее расширение другой допустимой программы. Для получения дополнительной информации о K см., например, константу Чайтина .

Мы говорим, что множество A натуральных чисел является K-тривиальным относительно константы b ∈ , если ${\displaystyle \mathbb {N} }$

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

Множество является K-тривиальным, если оно K-тривиально относительно некоторой константы. ^{[1] [2]}

Краткая история и развитие

На раннем этапе развития K-тривиальности внимание уделялось разделению K-тривиальных множеств и вычислимых множеств .

Хайтин в своей статье 1976 года ^[3] в основном изучал множества, такие, что существует b ∈ с ${\displaystyle \mathbb {N} }$

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

где C обозначает простую сложность Колмогорова . Эти множества известны как C-тривиальные множества. Хайтин показал, что они совпадают с вычислимыми множествами. Он также показал, что K-тривиалы вычислимы в проблеме остановки . Этот класс множеств обычно известен как множества в арифметической иерархии . ${\displaystyle \Delta _{2}^{0}}$

Роберт М. Соловей был первым, кто построил невычислимое K-тривиальное множество, в то время как попытка построения вычислимо перечислимого такого A была предпринята Калудом , Коулзом ^[4] и другими неопубликованными конструкциями Куммера K-тривиального и Мучника-младшего низкого для K множества.

События 1999–2008 гг.

В контексте теории вычислимости функция стоимости — это вычислимая функция

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

Для вычислимой аппроксимации множества A такая функция измеряет стоимость c ( n , s ) изменения аппроксимации до A(n) на этапе s. Первая конструкция функции стоимости была создана Кучерой и Тервейном. ^[5] Они построили вычислимо перечислимое множество, которое является низким для случайности Мартина-Лёфа, но не вычислимо. Их функция стоимости была адаптивной, в том смысле, что определение функции стоимости зависит от вычислимой аппроксимации строящегося множества. ${\displaystyle \langle A_{s}\rangle }$ ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Delta _{2}^{0}}$

Конструкция функции стоимости K-тривиального вычислимо перечислимого невычислимого множества впервые появилась в работе Дауни и др. ^[6]

Мы говорим, что множество A подчиняется функции стоимости c, если существует вычислимая аппроксимация A, ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \langle A_{s}:s\in \omega \rangle }$ ${\displaystyle S=\Sigma _{x,s}c(x,s)[x<s\wedge {\text{x is the least s.t. }}A_{s-1}(x)\neq A_{s}(x)]<\infty .}$

K-тривиальные множества характеризуются ^[7] подчинением стандартной функции стоимости, определяемой как

${\displaystyle c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}}$где ${\displaystyle K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}}$

и является s- м шагом в вычислимой аппроксимации фиксированной универсальной префиксной машины . ${\displaystyle \mathbb {U} _{s}}$ ${\displaystyle \mathbb {U} }$

Набросок конструкции невычислимого K-тривиального множества

На самом деле, набор можно сделать быстро простым. Идея состоит в том, чтобы удовлетворить требованиям быстрой простоты,

${\displaystyle PS_{e}:|W_{e}|=\infty \Rightarrow \exists s\exists x[x\in W_{e,s}\backslash W_{e,s-1}\wedge x\in A_{s}]}$

а также для поддержания низких затрат. Нам нужна функция затрат, чтобы удовлетворять предельному условию

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

а именно супремум по этапам стоимости для x стремится к 0 по мере увеличения x. Например, стандартная функция стоимости обладает этим свойством. Конструкция по сути ждет, пока стоимость не станет низкой, прежде чем помещать числа в для удовлетворения быстро простых требований. Мы определяем вычислимое перечисление таким образом, что ${\displaystyle A}$ ${\displaystyle \langle A_{s}:s\in \omega \rangle }$

${\displaystyle A_{0}=\emptyset }$. На этапе s > 0 для каждого e  <  s , если еще не выполнено и существует x  ≥ 2 e такое, что и , то мы помещаем x в и объявляем, что выполнено. Конец построения. ${\displaystyle PS_{e}}$ ${\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 .}$

Во-вторых, каждое требование выполняется: если бесконечно, то в силу того, что функция стоимости удовлетворяет предельному условию, некоторое число в конечном итоге будет включено в A, чтобы удовлетворить требованию. ${\displaystyle W_{e}}$

Эквивалентные характеристики

K-тривиальность оказывается совпадающей с некоторыми понятиями вычислительной малости, говорящими, что множество близко к вычислимому. Следующие понятия охватывают тот же класс множеств. ^[7]

Низость дляК

Мы говорим, что A является низким для K, если существует b ∈ такое, что ${\displaystyle \mathbb {N} }$

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

Вот префиксная колмогоровская сложность относительно оракула . ${\displaystyle K^{A}}$ ${\displaystyle A}$

Низкость для случайности Мартина-Лёфа

A имеет низкий уровень случайности Мартина-Лёфа ^[8], если всякий раз, когда Z является случайным по Мартину-Лёфу , оно уже является случайным по Мартину-Лёфу относительно A.

База для случайности Мартина-Лёфа

A является базой для случайности Мартина-Лёфа, если A сводимо по Тьюрингу к Z для некоторого множества Z , которое является случайным по Мартину-Лёфу относительно A. ^[7 ]

Были изучены и другие эквивалентные характеристики K-тривиальности, такие как:

1. Низкость для слабо-2-случайности;
2. Низкость для разности-левых-ce вещественных чисел (обратите внимание, что здесь не упоминается случайность).

Развитие событий после 2008 года

С 2009 года на сцену вышли концепции анализа. Это помогло решить некоторые печально известные проблемы.

Говорят, что множество Y является положительной точкой плотности, если каждый эффективно замкнутый класс, содержащий Y, имеет положительную нижнюю плотность Лебега в Y. Бьенвеню, Хельцль, Миллер и Нис ^[9] показали, что ML-случайное множество является неполным по Тьюрингу тогда и только тогда, когда оно является положительной точкой плотности. Дэй и Миллер ^[10] использовали это для утвердительного ответа на проблему ML-cupping: ^[11] A является K-тривиальным тогда и только тогда, когда для каждого случайного множества Мартина-Лёфа Z такого, что A⊕Z вычисляет проблему остановки , уже Z само по себе вычисляет проблему остановки .

Говорят, что множество Y является точкой плотности один, если каждый эффективно замкнутый класс, содержащий Y, имеет плотность Лебега 1 в Y. Любое случайное множество Мартина-Лёфа, которое не является точкой плотности один, вычисляет каждое K-тривиальное множество по Бьенвеню и др. ^[12] Дэй и Миллер показали, что существует случайное множество Мартина-Лёфа, которое является положительной точкой плотности, но не точкой плотности один. Таким образом, существует неполное такое случайное множество Мартина-Лёфа, которое вычисляет каждое K-тривиальное множество. Это утвердительно ответило на проблему покрытия, впервые поставленную Стефаном и затем опубликованную Миллером и Нисом. ^[13] Для краткости см. L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies и D. Turetsky. ^[14]

Были изучены варианты К-тривиальности:

• Тривиальные множества Шнорра, где машины имеют область определения с вычислимой мерой.
• сильно прослеживаемые множества скачков, свойство малости множеств, находящихся далеко внутри K-тривиальности.

Ссылки

1. А. Нис (2009). Вычислимость и случайность, Oxford Science Publications, ISBN  978-0199230761
2. Дауни, Родни Г., Хиршфельдт, Денис Р. (2010), «Алгоритмическая случайность и сложность», ISBN 978-0-387-68441-3 
3. Грегори Дж. Чайтин (1976), «Информационно-теоретические характеристики рекурсивных бесконечных строк», Теоретическая информатика, том 2, выпуск 1, июнь 1976 г., страницы 45–48
4. Кристиан Калуде, Ричард Дж. Коулз, Программно-размерная сложность начальных сегментов и сводимость доминирования, (1999), труды: Драгоценности навсегда, Вклад в теоретическую информатику в честь Арто Саломаа
5. Антонин Кучера и Себастьян А. Тервейн (1999), «Низкость для класса случайных множеств», Журнал символической логики, том 64, № 4 (декабрь 1999 г.), стр. 1396–1402
6. Род Г. Дауни, Денис Р. Хиршфельдт, Андре Нис, Фрэнк Стефан, «Тривиальные реалии», Электронные заметки по теоретической информатике 66, № 1 (2002), URL: «Elsevier.nl - de pagin kan niet worden weergegeven ". Архивировано из оригинала 3 октября 2005 г. Проверено 03 января 2014 г.
7. Андре Нис, (2005), «Свойства низших чисел и случайность», Успехи в математике , том 197, выпуск 1, 20 октября 2005 г., страницы 274–305
8. Антонин Кучера и Себастьян А. Тервейн (1999), «Низкость для класса случайных множеств», Журнал символической логики , том 64, № 4 (декабрь 1999 г.), стр. 1396–1402
9. Лоран Бьенвеню, Руперт Хёльцль, Джозеф С. Миллер и Андре Нис, (2012), «Альтернатива Данжуа для вычислимых функций», Труды 29-го Международного симпозиума по теоретическим аспектам компьютерной науки (STACS 2012), том 14 Лейбницских международных трудов по информатике, страницы 543–554. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.
10. Дж. Миллер, А. Дэй. (2012) «Каппинг со случайными наборами», опубликовано в Трудах Американского математического общества
11. Миллер и Нис, Случайность и вычислимость: открытые вопросы. Bull. Symb. Logic. 12 № 3 (2006) 390-410
12. Бьенвеню, Гринберг, Кучера, Нис и Турецкий, «K-тривиальность, случайность Обервольфаха и дифференцируемость», Mathematisches Forschungsinstitut Oberwolfach, Препринты Обервольфаха (OWP), ISSN  1864-7596
13. Миллер и Нис, Случайность и вычислимость: открытые вопросы. Bull. Symb. Logic. 12 № 3 (2006) 390–410
14. Вычисление K-тривиальных множеств с помощью неполных случайных множеств. Bull. Symbolic Logic. 20 марта 2014 г., стр. 80-90.