Давайте исправим кодировку машин Тьюринга и универсальной машины Тьюринга 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, а в противном случае ничего не делает. Можно изменить этот пример несколькими способами, чтобы получить контрпримеры для различных определений универсальных машин Тьюринга.
Ответы:
Просто расширенный комментарий без глубокого понимания: возможно, вы можете обмануть кодирование машины Тьюринга и создать искусственное кодирование, которое приведет к сюръективной колмогоровской сложности:
Соответствующая универсальная ТМ на входеб х проверяет, какова стоимость б , если это 0 тогда это просто выводит Икс+ 1 иначе имитирует ТМ Mх + 1 (M0 когда Икс пустая строка); Обратите внимание, чтоMх + 1 встраивает входы.
Для всех строкИкс , 1 ≤ K( х ) ≤ | х | + 1 ; и для всехn ≥ 1 есть 2N строки длины N но есть только 2n - 1- 1 программы длины < п которые могут быть представлены с помощью 1 р кодирующий; и только2N- 1 программы длины N которые могут быть представлены с помощью 1 р кодирующий; так хоть строкаИкс' длины N не может быть представлен программой 1 р длины ≤ n ; но это, безусловно, можно представить с помощью программы0Икс' длины n + 1 (мы не беспокоимся, если есть также программа 1 р одинаковой длины n + 1 это порождает это).
Мы можем сделать вывод, что для всехn > 1 существует строка Икс', |Икс'| =п такой, что К(Икс') = n + 1 (так что этот конкретный K сюръективен).
источник