Является ли колмогоровская сложность сюръективной функцией?

9

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

Существует ли N такое, что для всех n> N существует x с K (x) = n?

Замечание. Если мы определим универсальные машины Тьюринга по-другому, ответ может быть отрицательным. Например, рассмотрим U, который на входе (T, x) имитирует T на x, если длина (T, x) делится на 100, а в противном случае ничего не делает. Можно изменить этот пример несколькими способами, чтобы получить контрпримеры для различных определений универсальных машин Тьюринга.

domotorp
источник
Далеко не то, что вы просите, но я думаю, нетрудно доказать, что образ К имеет положительную линейную плотность независимо от U, Это подразумевает, например, чтоК(Икс)бесконечно часто составной.
Дэн Брумлев

Ответы:

3

Просто расширенный комментарий без глубокого понимания: возможно, вы можете обмануть кодирование машины Тьюринга и создать искусственное кодирование, которое приведет к сюръективной колмогоровской сложности:

  • 0 представляет машину Тьюринга, которая выводит 0 (1 состояние ТМ);
  • 0п представляет машину Тьюринга, которая выводит п+1 (число, представленное двоичной строкой пплюс один); это просто неявная «молниеносная» версия разрешимой ТМ, которая выводитп+1;
  • 1п представляет п+1ая машина Тьюринга в стандартном перечислении (перечисление может пропускать ТМ, уже включенные в 0 а также 0п).

Соответствующая универсальная ТМ на входе бИкс проверяет, какова стоимость б, если это 0 тогда это просто выводит Икс+1иначе имитирует ТМ MИкс+1 (M0 когда Икспустая строка); Обратите внимание, чтоMИкс+1 встраивает входы.

Для всех строк Икс, 1К(Икс)|Икс|+1; и для всехN1 есть 2N строки длины N но есть только 2N-1-1 программы длины <N которые могут быть представлены с помощью 1пкодирующий; и только2N-1 программы длины N которые могут быть представлены с помощью 1пкодирующий; так хоть строкаИкс' длины N не может быть представлен программой 1п длины N; но это, безусловно, можно представить с помощью программы0Икс' длины N+1 (мы не беспокоимся, если есть также программа 1п одинаковой длины N+1 это порождает это).

Мы можем сделать вывод, что для всех N>1существует строка Икс',|Икс'|знак равноN такой, что К(Икс')знак равноN+1 (так что этот конкретный K сюръективен).

Марцио де Биаси
источник