Есть много способов определить сложность Колмогорова , и обычно все эти определения они эквивалентны с точностью до аддитивной постоянной. То есть, если и являются функциями сложности Колмогорова (определяемыми через разные языки или модели), то существует постоянная такая, что для каждой строки , . Я полагаю, что это потому, что для любой колмогоровской функции сложности и для каждого она имеет , для некоторой константы .
Меня интересуют следующие определения для , основанные на машинах Тьюринга
- число состояний : определите как минимальное число такое, что TM с состояниями выводит на пустую строку.
- Длина программы : определите как самую короткую «программу», которая выводит . А именно, исправить способ кодирования ТМ в двоичные строки; для машины обозначим его (двоичный) , кодирующий , как . где минимум превышает все , которые выводят на пустой вход.
Являются и эквивалент? Какая связь между ними, и какая лучше понимает понятие колмогоровской сложности, если они не эквивалентны.
Что особенно меня увеличение скорости с , которая, по-видимому, не является суперлинейной (или, по крайней мере, линейной с постоянной такой, что , а не ). Рассмотрим самый простой TM, который выводит - тот, который просто кодирует как часть своих состояний и функций переходов. сразу видно, что . Однако кодировка той же машины намного больше, и полученная мной тривиальная оценка равна,
Ответы:
Я заранее прошу прощения за то, что даю слишком много деталей, но я собираюсь противоречить людям.
ОK(x)≤K′(x)+c
Тот факт, что обычно происходит от интерпретатора языка описания № 2 в язык описания № 1, а не от перевода программ № 2 в программы № 1.K1(x)≤K2(x)+c
Например, и вы получите это неравенство так же просто, как это:KC(x)≤KPython(x)+cpy2c
Тогда ваша константа будет примерно равна 528 + 490240688, где 528 - это число битов для этого кода, а 490240688 бит - это размер официального интерпретатора Python, написанного на C. Конечно, вам нужно только интерпретировать то, что возможно в ваш язык описания для Python, так что вы можете сделать лучше, чем 69 МБ :-)cpy2c 528+490240688 528 490240688
Важно то, что вы можете написать свою программу на Python линейно в своем C-коде. Например, язык, в котором вам нужно поместить «BANANA» между каждым символом, не очень хорошая программа описания, и тогда свойство имеет значение false. (Но если язык описания разрешает вам записывать данные в отдельный файл или в блок, эта проблема исчезнет)
Почему ваш имеет недостаткиK1(x)=q
Проблема с вашим определением состоит в том, что вам может потребоваться более q бит для описания машины Тьюринга с q состояниями, потому что вам нужно кодировать переходы.K1 q q
Таким образом, нет и K 2 , вероятно, не эквивалентны, но это в основном вина K 1 . Я думаю , что мы можем доказать , что для всех а > 0 существует с таким , что K 1 ( х ) ≤ | х | + c a . Конечно, любого a < 1 достаточно, чтобы опровергнуть тот факт, что K 1 не является допустимой функцией, поскольку это будет означать, что мы можем кодировать больше всех 2 n возможных строк длиныK1 K2 K1 a>0 ca K1(x)≤a|x|+ca a<1 K1 2n в виде п + гр через бит.n an+ca
Но размер невероятно тесен при сборке машин Тьюринга. Идея состоит в том, что в блоке состояний есть b 2 b способов найти переходы для каждого состояния, и это лучше, чем обычные 2 b способы, которыми вы можете заполнить b бит. Затем вы можете хранить в каждом блоке журнала 2 б бит информации. (не 2 log 2 b, потому что вы должны входить и выходить из блока так или иначе)b b2b 2b b log2b 2log2b
Так что да ... С блоками размером вы, вероятно, могли бы доказать K 1 ( x ) ≤ a | х | + c a . Но я уже написал слишком много о том, почему число состояний не является допустимой функцией сложности Колмогорова. Если вы хотите, чтобы я уточнил, я сделаю.21/a K1(x)≤a|x|+ca
Теперь оK2
Наивные описательный язык примерно соответствует (т.е. войти 2 Q для каждого следующего состояния и сведения о записи и прекращения).K2(x)=q⋅2⋅(log2q+2) log2q
Как вы, кажется, убеждены, что лучшим способом обмана было бы авторизация для кодирования «данных» в машину Тьюринга, возможно, путем добавления двоичного тега на языке описания, который говорит, является ли состояние состоянием данных ( который просто пишет немного и переходит в следующее состояние) или, если он делает что-то еще. Таким образом, вы можете хранить один бит вашего в одном бите вашего описательного языка.x
Однако, если вы сохраняете тот же самый вы можете использовать ту же технику, которую я использовал в предыдущей части, чтобы сохранить несколько битов, но я, похоже, застрял на K 2 ( x ) ≤ a | х | журнал | х | + c (для любого a > 0 ) .. возможно меньше чем log | х | даже, но получение O ( | x | ) кажется трудным. (И я ожидаю, что это должно быть | x | , даже не O ( |K2 K2(x)≤a|x|log|x|+c a>0 log|x| O(|x|) |x| .)O(|x|)
источник