Эквивалентность определений Колмогорова-Сложности

20

Есть много способов определить сложность Колмогорова , и обычно все эти определения они эквивалентны с точностью до аддитивной постоянной. То есть, если K1 и K2 являются функциями сложности Колмогорова (определяемыми через разные языки или модели), то существует постоянная c такая, что для каждой строки x , |K1(x)K2(x)|<c . Я полагаю, что это потому, что для любой колмогоровской функции сложности K и для каждого x она имеетK(x)|x|+c , для некоторой константыc .

Меня интересуют следующие определения для K , основанные на машинах Тьюринга

  1. число состояний : определите K1(x) как минимальное число q такое, что TM с q состояниями выводит x на пустую строку.
  2. Длина программы : определите K2(x) как самую короткую «программу», которая выводит x . А именно, исправить способ кодирования ТМ в двоичные строки; для машины M обозначим его (двоичный) , кодирующий , как M . K2(x)=min|M|где минимум превышает все , которые выводят на пустой вход.Mx

Являются и эквивалент? Какая связь между ними, и какая лучше понимает понятие колмогоровской сложности, если они не эквивалентны.K1K2

Что особенно меня увеличение скорости с , которая, по-видимому, не является суперлинейной (или, по крайней мере, линейной с постоянной такой, что , а не ). Рассмотрим самый простой TM, который выводит - тот, который просто кодирует как часть своих состояний и функций переходов. сразу видно, что . Однако кодировка той же машины намного больше, и полученная мной тривиальная оценка равна,K2xC>1K2<C|x||x|+cxxK1(x)|x|+1K2(x)|x|log|x|

Ран Г.
источник
Существует более машин с n состояниями, и их средний размер составляет не менее n 2 , поэтому маловероятно, что они отличаются только аддитивной константой. 2n2nn2
Каве
1
Хорошо известна оценка, что для некоторого фиксированного с, не зависящего от х . Это потому, что мы можем кодировать x в язык без префиксов, просто удваивая каждый бит x и заканчивая 01 . Это занимает 2 | х | + 2 бита для представления х . Таким образом, поскольку K 2 определяется в терминах универсальной машины без префиксов, K 2 ( x )K2(x)c+2|x|cxxx012|x|+2xK2 для некоторого фиксированного c . Это можно улучшить, используя более интеллектуальный способ кодирования x в язык без префиксов. K2(x)2|x|+2+ccx
Карл Маммерт
Я не вижу как. Похоже, что либо задается как часть кодировки (как необработанные данные), либо вы должны создать x с помощью конечного автомата. Первый вариант, кажется, обманывает, и я не вижу, как он может быть сопоставим со вторым вариантом (что подразумевает K 1 )xxK1
Ран Г.
@Ran G .: Ключевой момент - теорема об инвариантности, описанная на en.wikipedia.org/wiki/Invariance_theorem . Если я могу описать любую эффективную систему, которая имеет темп роста тогда универсальная машина Тьюринга (как вы описываете для K 2 ) встретит это в аддитивной константе. Универсальная машина является один , который принимает M является вводом и возвращает результат , M , если M привалы. 2|x|K2MMM
Карл Маммерт

Ответы:

6

Я заранее прошу прощения за то, что даю слишком много деталей, но я собираюсь противоречить людям.

О K(x)K(x)+c

Тот факт, что обычно происходит от интерпретатора языка описания № 2 в язык описания № 1, а не от перевода программ № 2 в программы № 1.K1(x)K2(x)+c

Например, и вы получите это неравенство так же просто, как это:KC(x)KPython(x)+cpy2c

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Тогда ваша константа будет примерно равна 528 + 490240688, где 528 - это число битов для этого кода, а 490240688 бит - это размер официального интерпретатора Python, написанного на C. Конечно, вам нужно только интерпретировать то, что возможно в ваш язык описания для Python, так что вы можете сделать лучше, чем 69 МБ :-)cpy2c528+490240688528490240688

Важно то, что вы можете написать свою программу на Python линейно в своем C-коде. Например, язык, в котором вам нужно поместить «BANANA» между каждым символом, не очень хорошая программа описания, и тогда свойство имеет значение false. (Но если язык описания разрешает вам записывать данные в отдельный файл или в блок, эта проблема исчезнет)

Почему ваш имеет недостаткиK1(x)=q

Проблема с вашим определением состоит в том, что вам может потребоваться более q бит для описания машины Тьюринга с q состояниями, потому что вам нужно кодировать переходы.K1qq

Таким образом, нет и K 2 , вероятно, не эквивалентны, но это в основном вина K 1 . Я думаю , что мы можем доказать , что для всех а > 0 существует с таким , что K 1 ( х ) | х | + c a . Конечно, любого a < 1 достаточно, чтобы опровергнуть тот факт, что K 1 не является допустимой функцией, поскольку это будет означать, что мы можем кодировать больше всех 2 n возможных строк длиныK1K2K1a>0caK1(x)a|x|+caa<1K12n в виде п + гр через бит.nan+ca

Но размер невероятно тесен при сборке машин Тьюринга. Идея состоит в том, что в блоке состояний есть b 2 b способов найти переходы для каждого состояния, и это лучше, чем обычные 2 b способы, которыми вы можете заполнить b бит. Затем вы можете хранить в каждом блоке журнала 2 б бит информации. (не 2 log 2 b, потому что вы должны входить и выходить из блока так или иначе)bb2b2bblog2b2log2b

Так что да ... С блоками размером вы, вероятно, могли бы доказать K 1 ( x ) a | х | + c a . Но я уже написал слишком много о том, почему число состояний не является допустимой функцией сложности Колмогорова. Если вы хотите, чтобы я уточнил, я сделаю.21/aK1(x)a|x|+ca

Теперь о K2

Наивные описательный язык примерно соответствует (т.е. войти 2 Q для каждого следующего состояния и сведения о записи и прекращения).K2(x)=q2(log2q+2)log2q

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

Однако, если вы сохраняете тот же самый вы можете использовать ту же технику, которую я использовал в предыдущей части, чтобы сохранить несколько битов, но я, похоже, застрял на K 2 ( x ) a | х | журнал | х | + c (для любого a > 0 ) .. возможно меньше чем log | х | даже, но получение O ( | x | ) кажется трудным. (И я ожидаю, что это должно быть | x | , даже не O ( |K2K2(x)a|x|log|x|+ca>0log|x|O(|x|)|x| .)O(|x|)

jmad
источник
Вы утверждаете, что не является функцией колмогоровской сложности? Это очень удивительно для меня, так как K 1 на самом деле является определением, используемым в некотором введении к курсу вычислимости, которое я когда-то брал (не то, что он говорит о его правильности). K1K1
Ран Г.
Хорошо то, что довольно тревожно. Учтите это: есть2nвозможных слов изnбитов, и вы можете кодировать их, используя1K1(x)12|x|+c2nnбит? Это означало бы2n=O(2 112n+c(ваша кодировка должна быть инъективной)2n=O(212n)
jmad
Что если в программе на python есть символы, зарезервированные C?
PyRulez