Сравнение колмогоровской сложности теорий

14

Теорема Чайтена о неполноте говорит, что никакая достаточно сильная теория арифметики не может доказать где K ( s ) - колмогоровская сложность строки s, а L - достаточно большая постоянная. L является достаточно большим , если он больше , чем размер в битах пробной проверки машины (PCM). РСМ для теории T принимает строку , закодированную как целое число в качестве входных данных и выводит 1 , если строка является допустимым доказательством на языке T .K(s)>LK(s)sLLTT

Предположим, что для теории Т представляет собой верхний предел для сложности T . Рассмотрим следующую иерархию теорий: пусть базовая теория будет арифметикой Робинсона ( Q ). Дополнение Q все более сильными аксиомами полиномиальной ограниченной индукции. Пусть Q - теория теорем, доказуемых с помощью Q, и любая из этих ограниченных аксиом индукции. Предположим, мы можем определить L ( Q ) и L ( Q L(T)>|PCMT|TTQQQQL(Q) путем определения PCM для каждой теории.L(Q)

Я хочу рассмотреть усовершенствованную машину проверки корректности (EPCM) для . Этот EPCM принимает строку в качестве входных данных точно так же, как ECM, и имеет второй вход, который определяет ранг и уровень под-теории Q . Если входная строка является действительным доказательством в Q ∗, EPCM проходит через этапы доказательства, чтобы определить самый высокий ранг и уровень используемой индукции. Затем этот EPCM записывает 1, если входное предложение является действительным доказательством в указанной под-теории Q .QQQQ

Реализована ли улучшенная проверка корректности, которую я описываю? Если это так, будет ли размер этого EPCM верхним пределом не только для сложности , но также и верхним пределом сложности любой под-теории Q ?QQ

Разумно ли говорить, что существует постоянная верхняя оценка сложности и всех его подтеорий?Q


Этот вопрос был вдохновлен несостоятельным доказательством Нельсона несостоятельности арифметики. Я не говорил об этом раньше, потому что некоторые люди находят это доказательство тревожным. Моя мотивация - задать интересный вопрос. CSTheory, кажется, правильный форум для этого вопроса. Сложность и всех его подтеорий либо ограничена константой, либо не ограничена. Любой ответ приводит к большему количеству вопросов.Q

Если сложность под-теорий не ограничена, мы можем задавать вопросы, например, что является самой слабой под-теорией в Q более сложной, чем ? Или сложнее, чем PA и ZFC? Размышление над этим вопросом уже показало мне, что существует серьезное ограничение на то, сколько теория может доказать о колмогоровской сложности струн. Если Q согласовано, то ни одна из его подтеорий не может доказать K ( s ) > L ( Q ) для любой строки. Это означает, что даже действительно сильные под-теории не могут доказать, что есть более сложные строки, чем некоторые более слабые под-теории, где более слабая теория более сложна, чем QQQK(s)>L(Q) .Q

Рассел Истерли
источник
1
Это правильно, насколько это возможно, но, конечно, дополнительный вклад ( , скажем), необходимый для проверки ограничения на индукционной схеме, сам по себе имеет неограниченную сложность, поэтому несколько ошибочно предположить, что вы ограничили эти сложности равномерно , n
Дополнительная сложность будет . Если мне потребуется n L, мне нужно будет только показать L > c + l o g ( L ) . log(n)nLL>c+log(L)
Рассел Истерли
Ваша запись несколько тревожно напоминает мне об этой неверной попытке доказать несостоятельность арифметики. Можете ли вы уточнить ваши мотивы?
Коди
Привет Рассел. Это звучит довольно интересно для меня. Если вы когда-нибудь хотели бы пообщаться, пожалуйста, дайте мне знать. Хорошего дня! :)
Майкл Вехар
Да, такая ТМ может использоваться для определения сложности теории. Я спрашиваю, есть ли ограничение на размер этой ТМ, когда у нас есть несколько теорий.
Рассел Истерли

Ответы:

5

Я постараюсь дать ответ на этот вопрос и постараюсь прояснить некоторую путаницу относительно точной формы вопроса.

Первое , что я хочу сделать: в утверждении постоянной Чайтину, действительно , функция Т . В абсолютном смысле он монотонен в выраженности T : если L ( T ) - наименьшее натуральное число, для которого T K ( s ) T ) L ( T ) . Аргумент очень прост: если существуетLTTL(T) для любой строки s , то если T является непротиворечивой теорией сильнее, чем T ( T φ подразумевает T

TK(s)L(T)
sTTTφ для любого арифметического предложения φ ), тогда L ( s , для которого T K ( s ) L, то T K ( s ) L по условию.TφφL(T)L(T)sTK(s)LTK(s)L

Однако это верно только в том случае, если является абсолютной постоянной Хайтина. В частности, если T доказывает C o n ( T ) , то T L s T K ( ¯ sL(T)TCon(T)

TLs TK(s¯)L¯

усваивая аргумент Чейтина. Тем не менее , конкретный для которогоl

Ts TK(s¯)l¯

в общем случае не будет равен L(T) . В частности, оно может быть намного больше, обычно пропорциональноразмеру доказательстваCon(T) в T . Это можно легко увидеть в доказательстве самой теоремы, которая в решающей степени опирается на непротиворечивости .T

Таким образом, хотя может доказать непротиворечивость системы с ограниченной индукцией, длина этих доказательств тем больше, чем ближе вы подходите к Q QQ выразительности (один из способов понять теоремы неполноты состоит в том, что длина становится бесконечной, когда вы достигаете , таким образом, он не имеет конечного доказательства согласованности в самом Q ). Таким образом, то же самое относится к различным верхним оценкам на внутренних L ( T ) s Q ∗, которые можно описать для каждой под-теории.QQ L(T)Q

Итак, вот краткий ответ на ваш вопрос: ограничено равномерно для всех подтеорий Q , но сам Q не может показать, что эта оценка верна для всех таких подтеорий . Это была решающая ошибка, которую сделал Нельсон (похороненный под несколькими слоями формализма), и на которую Тао указал здесь .L(T)QQ

Коди
источник
ПРА может доказать . Является ли размер этого доказательства верхней границей сложностиCon(Q) и всех его подтеорий (при условии совместимого кодирования аксиом, предложений и т. Д.)? Q
Рассел Истерли
PRA может дать равномерную оценку для для каждой из под-теорий. поскольку P R AC o n ( Q ) и для любой подсистемы T из Q , P R AC o n ( Q ) C o nLPRACon(Q)TQ , и поэтому нетрудно показать что оценка для Q также работает для T (в рамках PRA). PRACon(Q)Con(T)QT
Коди
Под любой под-теорией I, конечно, подразумевается любая под-теория, которая может быть доказана в PRA. Q
Коди
Привет, Коди, спасибо за ответ. Надеюсь все хорошо. :)
Майкл Вехар
1
Спасибо, Майк! Это был забавный вопрос. Тот факт, что сам Нельсон запутался в деталях, говорит о том, что на этом пути есть некоторые тонкие подводные камни ...
Коди