Давайте исправим кодирование без Трекинга машин Тьюринга и универсальную машину Тьюринга которая на входе (закодированный как код без префиксов последующим ) выводит все выходные данные на входе x (возможно, оба бегают вечно). Определим колмогоровскую сложность x , K (x) как длину самой короткой программы p такой, что U (p) = x .U
Существует ли машина Тьюринга такая, что для каждого входа выводится целое числоэто отличается от колмогоровской сложности , т. е. но ?
T x T(x)≤|x| x T(x)≠K(x) лим инф | х | → ∞ T ( x ) = ∞lim inf|x|→∞T(x)=∞
Условия необходимы, потому что
(а) если T ( x ) ≰ | х |
(b) если лим инф | х | → ∞ T ( x ) < C
Также обратите внимание, что наша работа была бы легкой, если бы мы знали, что Т ( х )
Я знаю, что отношения изучены в целом, но
Кто-нибудь когда-нибудь задавал подобный вопрос, где наша цель - дать алгоритм, который не выводит какой-либо параметр?
Моя мотивация - это проблема http://arxiv.org/abs/1302.1109 .
Ответы:
Вопрос можно перефразировать следующим образом: , и как указывает Денис в комментариях это неверно для некоторых кодировок. Вот более слабое утверждение и попытка его доказательства, которое не зависит от каких-либо деталей кодировки, но я для простоты предположу бинарный язык:Лим Инф | х | → ∞ | Т ( х ) - К ( х ) | = 0liminf|x|→∞|T(x)−K(x)|=0
Пусть - вычислимая функция, удовлетворяющая и . Тогда . Неофициально, если вокруг колмогоровской сложности каждой строки есть цель, которая неограниченно растет, никакая вычислимая функция не может избежать ее попадания.T : { 0 , 1 } ∗ → N 0 ≤ T ( x ) ≤ | х | Лим Инф | х | → ∞ T ( x ) = ∞ lim inf | х | → ∞ | Т ( х ) - К ( х ) | < ∞T:{0,1}∗→N 0≤T(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 nn b 0≤n<2b K(n)≥b b n b |{T(x)=b}|≥2b T x nth T(x)=b c1 K(x)>b−c1 K(n)≥b n может быть вычислено из . И существует константа такая, что , потому что также ограничена сверху только константой больше, чем , и может быть вычислено из . Тогда , и у нас есть бесконечное число вариантов для (те, у которых прообраз кардинальности не менее ), что дает бесконечное число значений для , так что мы сделали.x c 2 K ( x ) < b + c 2 K ( n ) b x n | К ( х ) - Т ( х ) | < c 1 + c 2 b 2 b xx c2 K(x)<b+c2 K(n) b x n |K(x)−T(x)|<c1+c2 b 2b x
Подразумевается, что для некоторых , бесконечно часто. Так что можно сказать, что мы не можем не выводить что-то, что не является колмогоровской сложностью!c ∈ Z T ( x ) = K ( x ) + cc∈Z T(x)=K(x)+c
источник
Я думаю, что следующие работы. Я буду использовать C ( x ) для сложности КолмогороваC(x)
источник