Эффективный размер - Effective dimension

В математика, эффективное измерение это модификация Хаусдорфово измерение и другие фрактальные измерения что помещает его в теория вычислимости настройка. Существует несколько вариантов (различные понятия эффективной размерности), наиболее распространенной из которых является эффективное хаусдорфово измерение. Размер в математике - это особый способ описания размера объекта (в отличие от меры и других, различных понятий размера). Измерение Хаусдорфа обобщает хорошо известные целочисленные измерения, присвоенные точкам, линиям, плоскостям и т. Д., Позволяя различать объекты промежуточного размера между этими целочисленными объектами. Например, фрактал подмножества плоскости могут иметь промежуточный размер от 1 до 2, поскольку они «больше», чем линии или кривые, и все же «меньше», чем закрашенные круги или прямоугольники. Эффективная размерность изменяет размерность Хаусдорфа, требуя, чтобы объекты с малой эффективной размерностью были не только маленькими, но и размещаемыми (или частично размещаемыми) в вычислимом смысле. Таким образом, объекты с большой размерностью Хаусдорфа также имеют большую эффективную размерность, а объекты с малой эффективной размерностью имеют малую размерность Хаусдорфа, но объект может иметь малую размерность Хаусдорфа, но большую эффективную размерность. Примером является алгоритмически случайный точка на прямой, имеющая размерность Хаусдорфа 0 (поскольку это точка), но эффективная размерность 1 (потому что, грубо говоря, она не может быть эффективно локализована лучше, чем небольшой интервал, имеющий размерность Хаусдорфа 1).

Строгие определения

В этой статье будет определено эффективное измерение для подмножеств Канторовское пространство 2ω; тесно связанные определения существуют для подмножеств Евклидово пространство рп. Мы будем свободно перемещаться между рассмотрением набора Икс натуральных чисел, бесконечная последовательность задается характеристической функцией Икс, и действительное число с двоичным расширением 0.Икс.

Мартингалы и другие штормы

А мартингейл на пространстве Кантора 2ω это функция d: 2ω → р≥ 0 из пространства Кантора в неотрицательные числа, удовлетворяющие условию справедливости:

Мартингейл рассматривается как стратегия ставок, а функция дает капитал лучших после просмотра последовательности σ нулей и единиц. Тогда условие справедливости говорит, что капитал после последовательности σ является средним значением капитала после просмотра σ0 и σ1; Другими словами, мартингейл дает схему ставок для букмекера с коэффициентом 2: 1, предлагаемым на любой из двух «равновероятных» вариантов, отсюда и название справедливое.

(Обратите внимание, что это немного отличается от представления теории вероятностей о мартингейл.[1] Это определение мартингейла имеет аналогичное условие справедливости, которое также гласит, что ожидаемое значение после некоторого наблюдения такое же, как и значение до наблюдения, с учетом предшествующей истории наблюдений. Разница в том, что в теории вероятностей предыдущая история наблюдений относится только к истории капитала, тогда как здесь история относится к точной последовательности нулей и единиц в строке.)

А супермартингейл на канторовом пространстве - функция d как указано выше, которое удовлетворяет модифицированному условию справедливости:

Супермартингейл - это стратегия ставок, при которой ожидаемый капитал после ставки не превышает капитала до ставки, в отличие от мартингейла, в котором эти два капитала всегда равны. Это обеспечивает большую гибкость и очень похоже на неэффективный случай, поскольку всякий раз, когда супермартингейл d дано, есть модифицированная функция d ' который приносит как минимум столько же денег, сколько d и который на самом деле является мартингалом. Однако полезно предоставить дополнительную гибкость, как только кто-то начнет говорить о фактическом предоставлении алгоритмов для определения стратегии ставок, поскольку некоторые алгоритмы более естественны для создания супермартингалов, чем мартингейлов.

An s-шторм это функция d как указано выше в форме

для е какой-то мартингейл.

An s-супергейл это функция d как указано выше в форме

для е какой-то супермартингейл.

An s- (Супер) шторм - это стратегия ставок, при которой некоторая сумма капитала теряется из-за инфляции на каждом этапе. Обратите внимание, что s-галес и s-супергейлы являются примерами супермартингалов, а 1-галлы и 1-супергейлы - это именно мартингалы и супермартингалы.

В совокупности эти объекты известны как «штормы».

Буря d преуспевает на подмножестве Икс натуральных чисел, если где обозначает п-цифровая строка, состоящая из первых п цифры Икс.

Буря d сильно преуспевает на Икс если .

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

Буря d называется конструктивный, c.e., или низко вычислимый если числа равномерно лево в. п. вещественные числа (т.е. могут быть равномерно записаны как предел возрастающей вычислимой последовательности рациональных чисел).

В эффективное хаусдорфово измерение набора натуральных чисел Икс является .[2]

В эффективный размер упаковки из Икс является .[3]

Колмогоровское определение сложности

Колмогоровская сложность можно рассматривать как нижнюю границу алгоритмической сжимаемости конечной последовательности (символов или двоичных цифр). Каждой такой последовательности он присваивает ш натуральное число К (Вт) который интуитивно измеряет минимальную длину компьютерной программы (написанной на каком-то фиксированном языке программирования), которая не требует ввода и выводит ш при запуске.

В эффективное хаусдорфово измерение набора натуральных чисел Икс является .[4][5][6][7]

В эффективный размер упаковки набора Икс является .[3][4][5]

Из этого можно видеть, что и эффективный размер Хаусдорфа, и эффективный размер упаковки набора находятся между 0 и 1, причем эффективный размер упаковки всегда по крайней мере такой же, как эффективный размер Хаусдорфа. Каждые случайная последовательность будут иметь эффективные размеры Хаусдорфа и упаковки, равные 1, хотя существуют также неслучайные последовательности с эффективными размерами Хаусдорфа и упаковки, равными 1.

Сравнение с классическим размером

Если Z это подмножество 2ω, его размерность Хаусдорфа равна .[2]

Размер упаковки Z является .[3]

Таким образом, эффективный Хаусдорф и размер упаковки набора являются просто классическими размерами Хаусдорфа и упаковки (соответственно), когда мы ограничиваем наше внимание к. п. штормы.

Определите следующее:

Следствием вышесказанного является то, что все они имеют размерность Хаусдорфа. .[8]

и все имеют размер упаковки 1.

и все имеют размер упаковки .

использованная литература

  1. ^ Джон М. Хичкок; Джек Х. Лутц (2006). «Почему вычислительная сложность требует более строгих мартингалов». Теория вычислительных систем.
  2. ^ а б Джек Х. Лутц (2003). «Размерность в классах сложности». SIAM Журнал по вычислениям. 32 (5): 1236–1259. arXiv:cs / 0203016. Дои:10.1137 / s0097539701417723.
  3. ^ а б c Кришна Б. Атрейя; Джон М. Хичкок; Джек Х. Лутц; Эльвира Майордомо (2007). «Эффективное сильное измерение алгоритмической информации и вычислительной сложности». SIAM Журнал по вычислениям. 37 (3): 671–705. arXiv:cs / 0211025. Дои:10.1137 / s0097539703446912.
  4. ^ а б Цзинь-и Цай; Юрис Хартманис (1994). "О хаусдорфовой и топологической размерности колмогоровской сложности вещественной прямой". Журнал компьютерных и системных наук. 49 (3): 605–619. Дои:10.1016 / S0022-0000 (05) 80073-X.
  5. ^ а б Людвиг Штайгер (1993). «Колмогоровская сложность и хаусдорфова размерность». Информация и вычисления. 103 (2): 159–194. Дои:10.1006 / inco.1993.1017.
  6. ^ Эльвира Майордомо (2002). "Характеристика колмогоровской сложности конструктивной хаусдорфовой размерности". Письма об обработке информации. 84: 1–3. Дои:10.1016 / S0020-0190 (02) 00343-5.
  7. ^ Людвиг Штайгер (2005). «Конструктивная размерность равна колмогоровской сложности». Письма об обработке информации. 93 (3): 149–153. Дои:10.1016 / j.ipl.2004.09.023.
  8. ^ Борис Рябко (1994). «Кодирование комбинаторных источников и размерность Хаусдорфа». Советская математика - Доклады.
  • Дж. Х. Лутц (2005). «Эффективные фрактальные размерности». Mathematical Logic Quarterly. 51 (1): 62–72. CiteSeerX  10.1.1.143.7654. Дои:10.1002 / malq.200310127. [1]
  • Дж. Рейманн (2004). «Вычислимость и фрактальная размерность, кандидатская диссертация». Ruprecht-Karls Universität Heidelberg. Цитировать журнал требует | журнал = (Помогите) [2]
  • Л. Штайгер (2007). «Колмогоровская сложность бесконечных слов». Теоретическая информатика. 383 (2–3): 187–199. Дои:10.1016 / j.tcs.2007.04.013. [3]