Разве мы не можем вывести колмогоровскую сложность?

28

Давайте исправим кодирование без Трекинга машин Тьюринга и универсальную машину Тьюринга которая на входе (закодированный как код без префиксов последующим ) выводит все выходные данные на входе x (возможно, оба бегают вечно). Определим колмогоровскую сложность x , K (x) как длину самой короткой программы p такой, что U (p) = x .U U( T , x ) (T,x)T Tx xT Tx xx xK ( x ) K(x)p pU ( p ) = xU(p)=x

Существует ли машина Тьюринга такая, что для каждого входа выводится целое числоэто отличается от колмогоровской сложности , т. е. но ?TxT(x)|x|xT(x)K(x)лим инф | х | T ( x ) = lim inf|x|T(x)=

Условия необходимы, потому что

(а) если T ( x ) | х |T(x)|x|тогда было бы легко вывести число, которое тривиально отличается от К ( х )K(x) потому что оно больше, чем | х | + с U|x|+cU ,

(b) если лим инф | х | T ( x ) < Clim inf|x|T(x)<C , то мы можем просто вывести 00 (или некоторую другую константу) почти для всех чисел, «к счастью» угадав не более одного (конечное число), которые оцениваются в 00 (в какую-то другую константу) и выводят туда что-то еще. Мы даже можем гарантировать лим суп | х | T ( x ) = lim sup|x|T(x)= , выводя что-то вроде 2 log n2logn для х = 2 нx=2n .

Также обратите внимание, что наша работа была бы легкой, если бы мы знали, что Т ( х )T(x) не сюръективна, но об этом мало что известно , поэтому ответ может зависеть от UU , хотя я сомневаюсь, что так и будет.

Я знаю, что отношения изучены в целом, но

Кто-нибудь когда-нибудь задавал подобный вопрос, где наша цель - дать алгоритм, который не выводит какой-либо параметр?

Моя мотивация - это проблема http://arxiv.org/abs/1302.1109 .

domotorp
источник
5
Это зависит от вашей кодировки, так как, как упоминалось в теме о сюръективности вы ссылаетесь, может быть так, что допустимы только программы четной длины. Поэтому, чтобы сделать ваш вопрос нетривиальным, вам нужно иметь больше гипотез о кодировке. К рKp
Денис
2
На ваш второй вопрос: да. Учитывая целое число , пусть обозначает машину Тьюринга. По диагонали нерекурсивна функция (или DNR) является функцией такое , что для всех целых чисел , . (То есть, если останавливается на , то , а в противном случае может быть произвольным.) Они были совсем недавно изучены в области вычислимости / вычислимости случайность сообщества. Google "по диагонали не рекурсивный", чтобы найти документы по этому вопросу. M [ M ] M f : NN M [ M ] ( M ) f ( M ) [ M ] M f ( M ) [ M ] ( M ) f ( M )M[M]Mf:NNM[M](M)f(M)[M]Mf(M)[M](M)f(M)
Джошуа Грохов
1
@ Денис: я думаю, что вы не правы. Согласно моему определению универсальных машин Тьюринга, приведенному в первом параграфе, все длины могут быть допустимыми программами.
Domotorp
3
Несколько раз назад я думал (напрасно) о, казалось бы простой вариант: (DIS) , доказывающие , что при достаточно большом , для всех . х 0 К ( х ) | х | / 2 x x 0x0K(x)|x|/2xx0
Марцио де Биаси,
1
@ Рики: Хорошо, у меня нет ограничений на кодировки машин Тьюринга, только на программы, которые вы можете прочитать в первом параграфе.
Domotorp

Ответы:

7

Вопрос можно перефразировать следующим образом: , и как указывает Денис в комментариях это неверно для некоторых кодировок. Вот более слабое утверждение и попытка его доказательства, которое не зависит от каких-либо деталей кодировки, но я для простоты предположу бинарный язык:Лим Инф | х | | Т ( х ) - К ( х ) | = 0liminf|x||T(x)K(x)|=0

Пусть - вычислимая функция, удовлетворяющая и . Тогда . Неофициально, если вокруг колмогоровской сложности каждой строки есть цель, которая неограниченно растет, никакая вычислимая функция не может избежать ее попадания.T : { 0 , 1 } N 0 T ( x ) | х | Лим Инф | х | T ( x ) = lim inf | х | | Т ( х ) - К ( х ) | < T:{0,1}N0T(x)|x|liminf|x|T(x)=liminf|x||T(x)K(x)|<

Чтобы увидеть это, пусть будет случайным битным числом, то есть и . Для всех такой случайный существует. Также отметим , что существует бесконечное число значений , для которых , это следует из условий , размещенных на . Теперь пусть будет наименьшей строкой такой, что . Ясно, что существует константа такая, что , потому что иn b 0 n < 2 b K ( n ) b b n b | { T ( x ) = b } | 2 b T x n th T ( x ) = b c 1 K ( x ) > b - c 1 K ( n ) b nnb0n<2bK(n)bbnb|{T(x)=b}|2bTxnthT(x)=bc1K(x)>bc1K(n)bnможет быть вычислено из . И существует константа такая, что , потому что также ограничена сверху только константой больше, чем , и может быть вычислено из . Тогда , и у нас есть бесконечное число вариантов для (те, у которых прообраз кардинальности не менее ), что дает бесконечное число значений для , так что мы сделали.x c 2 K ( x ) < b + c 2 K ( n ) b x n | К ( х ) - Т ( х ) | < c 1 + c 2 b 2 b xxc2K(x)<b+c2K(n)bxn|K(x)T(x)|<c1+c2b2bx

Подразумевается, что для некоторых , бесконечно часто. Так что можно сказать, что мы не можем не выводить что-то, что не является колмогоровской сложностью!c Z T ( x ) = K ( x ) + ccZT(x)=K(x)+c

Дан Брумлев
источник
1
Хорошо, я думаю, это должно сработать. Конечно, не может быть никаких строк с , поэтому, возможно, вы захотите потребовать , верно? f ( x ) = b f ( x ) bf(x)=bf(x)b
Domotorp
1
Это должно быть так что вычислимо из . Итак, я думаю, что нужно выбрать так, чтобы или около того строки соответствовали ему. Предположительно, предположения должны подразумевать, что таких бесконечно много (хотя я не совсем вижу это в данный момент). (Насколько я могу судить, предположения не использовались никаким другим способом.)f(x)=bf(x)=bnnxb,nxb,n bb2b+12b+1bb
Эмиль Йержабек поддерживает Монику
1
Да, действительно, это необходимо. Но доказательство легко от противного: если оно всегда < 2 b, если b > b 0 , то, взглянув на любой диапазон b 0 < b B , мы можем заключить, что по крайней мере B - b 0 строк отображаются в b 0 , то есть бесконечно много, что противоречит lim inf = . <2bb>b0b0<bBBb0b0lim inf=
domotorp
То, о чем говорит Денис, не относится к тому, как я определил универсальность в первой строке моего вопроса. Его замечание также тривиально, я понятия не имею, почему так много людей проголосовали за его комментарий. Но, увы, неправильный ответ Питера получил так много откликов, что я теряю веру в этот сайт ...
domotorp
Не имеет значения, как закодированы ТМ, если мои критерии относительно универсальной ТМ удовлетворены, поэтому комментарий Дениса неверен. Если бы это было высказано как замечание о другой модели, то это было бы другое. Во всяком случае, вместо того , чтобы хандрить по этому поводу, давайте попробуем посмотреть , если мы сможем укрепить свою идею ...
domotorp
3

Я думаю, что следующие работы. Я буду использовать C ( x ) для сложности КолмогороваC(x)

  • Дайте U временную границу t (скажем, некоторую экспоненциальную функцию длины входной программы) и назовите результат U t . Если программа превышает ограничение по времени, U t входит в бесконечный цикл.UtUtUt
  • Пусть C t ( x ) - самая короткая программа для x на t . Обратите внимание, что C t вычислимо.Ct(x)xtCt
  • Пусть T ( x ) возвращает C t ( x ) + 1 , если только это значение не равно | х | в этом случае верните 0. Если x не является выводом пустой программы, в этом случае верните 1.T(x)Ct(x)+1|x|x
  • Поскольку C ( x ) C t ( x ) , T ( x ) всегда будет отличаться от C ( x ) . Логика предыдущего шага заботится о крайних случаях.C(x)Ct(x)T(x)C(x)
  • U t функционирует как код для всех строк, поэтому он имеет ограничение на бесконечность.Ut
Питер
источник
несколько комментариев, теория KC в качестве альтернативы (но эквивалент) интерпретация гласит следующее: Почти все строки уже находятся в их оптимальном представлении ( WRT для данной модели) , за исключением счетного множества строк , которые могут быть преобразованы в оптимальное представление (минимум) WRT для данной модели вычислений (или ТМ). В этом смысле почти каждая программа выводит оптимальные строковые представления, но они не известны (или не могут быть вычислены) априори
Никос М.
Почему у вас будет T ( x ) | х | ? T(x)|x|
Домоторп
@domotorp Технически у нас есть T ( x ) | х | + c, где c - длина самой короткой программы печати. Конечно, эта константа также существует для C ( x ) (и на самом деле, если программа печати не очень медленная, это та же самая константа). T(x)|x|+ccC(x)
Питер
Но это то, что делает весь вопрос интересным! Я мог бы попросить любую функцию вместо | х | Например, | х | / 2 + 99 , моя единственная цель состояла в том, чтобы устранить решения, подобные вашим. |x||x|/2+99
domotorp
@domotrop Я вижу, поэтому вы хотите, чтобы T ( x ) не был верхним пределом C ( x ) . Это более интересно ...
Питер