K-тривиальное множество

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

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

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

Определение

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

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

\forall nK(A\upharpoonright n)\leq K(n)+b

.

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

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

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

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

\forall nC(A\upharpoonright n)\leq C(n)+b

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

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

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

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

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

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

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

Мы говорим $\Delta _{2}^{0}$ множество A подчиняется функции стоимости c, если существует вычислимая аппроксимация A, $\langle A_{s}:s\in \omega \rangle$ $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] согласно стандартной функции стоимости , определяемой формулой

c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}

где

K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}

и $\mathbb {U} _{s}$ — это s -й шаг в вычислимом приближении фиксированной универсальной машины без префиксов. $\mathbb {U}$ .

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

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

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}]

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

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

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

$A_{0}=\emptyset$ . На этапе s > 0 для каждого e < s , если $PS_{e}$ еще не встречалось и существует x ≥ 2 e такое, что $x\in W_{e,s}\backslash W_{e,s-1}$ и $c(x,s)\leq 2^{-e}$ , затем мы помещаем x в $A_{s}$ и заявить, что $PS_{e}$ встречается. Конец строительства.

Чтобы убедиться, что конструкция работает, сначала обратите внимание, что A подчиняется функции стоимости, поскольку в A для каждого требования входит не более одного числа. Таким образом, сумма S не превосходит

\Sigma _{e}2^{-e}<\infty .

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

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

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

Низкость для К

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

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

Здесь $K^{A}$ является беспрефиксной колмогоровской сложностью относительно оракула $A$ .

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

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

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

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

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

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

События после 2008 года

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

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

Говорят, что множество Y является точкой плотности один, если каждый эффективно замкнутый класс, содержащий Y, имеет плотность Лебега 1 в Y. Любой случайный набор Мартина-Лёфа, который не является точкой плотности один, вычисляет каждый K тривиальный набор по Бьенвеню и др. . ^[12] Дэй и Миллер показали, что существует случайное множество Мартина-Лёфа, которое является точкой положительной плотности, но не точкой плотности один. Таким образом, существует неполный такой случайный набор Мартина-Лёфа, который вычисляет каждый K-тривиальный набор. Это утвердительно ответило на проблему покрытия, впервые заданную Стефаном, а затем опубликованную Миллером и Найсом. ^[13] Резюме см. Л. Бьенвеню, А. Дей, Н. Гринберг, А. Кучера, Дж. Миллер, А. Нис и Д. Турецкий. ^[14]

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

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

Ссылки

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

[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 — страница не может быть отображена» . Архивировано из оригинала 3 октября 2005 г. Проверено 3 января 2014 г.

[AndreNies-7] Перейти обратно: ^а ^б ^с Андре Нис, (2005), «Свойства малости и случайность», « Достижения в математике» , том 197, выпуск 1, 20 октября 2005 г., страницы 274–305

[8] Антонин Кучера и Себастьян А. Тервейн (1999), «Низкость для класса случайных множеств», Журнал символической логики , Vol. 64, № 4 (декабрь 1999 г.), стр. 1396–1402.

[9] Лоран Бьенвеню, Руперт Хёльцль, Джозеф С. Миллер и Андре Нис (2012), «Альтернатива Данжуа для вычислимых функций», Труды 29-го Международного симпозиума по теоретическим аспектам информатики (STACS 2012), том 14 Лейбница Международные труды по информатике, страницы 543–554. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2012.

[10] Дж. Миллер, А. Дэй. (2012) «Купирование случайных наборов», появится в Трудах Американского математического общества.

[11] Миллер и Нис, Случайность и вычислимость: открытые вопросы. Бык. Симб. Логика. 12 № 3 (2006) 390-410

[12] Бьенвеню, Гринберг, Кучера, Нис и Турецкий, «K-тривиальность, случайность Обервольфаха и дифференцируемость», Институт математических исследований Обервольфаха, Препринты Обервольфаха (OWP), ISSN 1864-7596

[13] Миллер и Нис, Случайность и вычислимость: открытые вопросы. Бык. Симб. Логика. 12 № 3 (2006) 390–410

[14] Вычисление K-тривиальных множеств по неполным случайным наборам. Бык. Символическая логика. 20 марта 2014 г., стр. 80-90.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]