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

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

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

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

Определение

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

Мы говорим набор A натуральные числа K-тривиально через константу b ∈ ℕ, если

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

Множество K-тривиально, если оно K-тривиально через некоторую константу.^[1][2]

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

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

Чайтин в своей статье 1976 г. ^[3] в основном изучаемые множества такие, что существует b ∈ℕ с

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

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

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

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

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

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

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

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

Мы говорим ${\displaystyle \Delta _{2}^{0}}$ набор А подчиняется функции стоимости c если существует вычислимое приближение A, ${\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\}}$

и ${\displaystyle \mathbb {U} _{s}}$ это 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, для каждого е < s, если ${\displaystyle PS_{e}}$ еще не встречен и существует Икс ≥ 2е такой, что ${\displaystyle x\in W_{e,s}\backslash W_{e,s-1}}$ и ${\displaystyle c(x,s)\leq 2^{-e}}$, то положим Икс в ${\displaystyle A_{s}}$ и заявляем, что ${\displaystyle PS_{e}}$ встречается. Конец строительства.

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

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

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

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

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

Слабость для K

Мы говорим что А низкий для K Если там есть б ∈ ℕ такой, что

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

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

Слабость для случайности Мартина-Лёфа

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

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

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

^[7]

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

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

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

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

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

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

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

• Тривиальные множества Шнорра где у машин есть область с вычислимой мерой.
• сильно скачкообразные отслеживаемые множества, свойство малости множеств глубоко внутри 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, No. 4 (декабрь 1999 г.), стр. 1396–1402
6. Род Г. Дауни, Денис Р. Хиршфельдт, Андрэ Нис, Фрэнк Стефан, «Тривиальные реальности», Электронные заметки по теоретической информатике 66 № 1 (2002), URL: «Архивная копия». Архивировано из оригинал на 2005-10-03. Получено 2014-01-03.
7. Андре Нис, (2005), "Свойства малости и случайность", Успехи в математике, Volume 197, Issue 1, 20 октября 2005 г., страницы 274–305
8. Антонин Кучера и Себастьян А. Тервейн (1999), "Низкость класса случайных множеств", Журнал символической логики, Vol. 64, No. 4 (декабрь 1999 г.), стр. 1396–1402
9. Лоран Бьенвеню, Руперт Хёльцль, Джозеф С. Миллер и Андре Нис, (2012), «Альтернатива Данжуа для вычислимых функций», Труды 29-го Международного симпозиума по теоретическим аспектам информатики (STACS 2012), том 14 Leibniz International Труды по информатике, страницы 543–554. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2012.
10. Дж. Миллер, А. Дэй. (2012) «Купирование со случайными наборами», чтобы появиться в Трудах Американского математического общества
11. Миллер и Нис, Случайность и вычислимость: открытые вопросы. Бык. Симв. Логика. 12 № 3 (2006) 390-410
12. Бьенвеню, Гринберг, Кучера, Нис и Турецкий, "K-тривиальность, случайность Обервольфаха и дифференцируемость", Mathematisches Forschungsinstitut Oberwolfach, Препринты Обервольфаха (OWP), ISSN  1864-7596
13. Миллер и Нис, Случайность и вычислимость: открытые вопросы. Бык. Симв. Логика. 12 № 3 (2006) 390–410
14. Вычисление K-тривиальных множеств неполными случайными множествами. Бык. Символическая логика. 20, март 2014 г., стр. 80-90.