Следует ли невычислимость колмогоровской сложности из теоремы Лаврэ о неподвижной точке?

17

Многие теоремы и «парадоксы» - диагонализация Кантора, неразрешимость хетлинга, неразрешимость колмогоровской сложности, неполнота Гёделя, неполнота Хаитина, парадокс Рассела и т. Д. - все имеют по существу одно и то же доказательство диагонализацией (обратите внимание, что это более конкретно, чем то, что они могут все должно быть доказано диагонализацией, скорее, кажется, что все эти теоремы действительно используют одну и ту же диагонализацию; более подробную информацию см., например, Янофски , или для более краткого и менее формализованного изложения мой ответ на этот вопрос ).

В комментарии к вышеупомянутому вопросу Сашо Николов указал, что большинство из них были частными случаями теоремы Лаврэра о неподвижной точке . Если бы все они были особыми случаями, то это было бы хорошим способом уловить вышеупомянутую идею: на самом деле был бы один результат с одним доказательством (по закону Лаврэ), из которого все вышеперечисленное явилось прямым следствием.

Теперь, для Гёделя Неполнота и неразрешимость проблемы остановки и их друзей, хорошо известно, что они следуют из теоремы Лаврэса о неподвижной точке (см., Например, здесь , здесь или Янофски ). Но я не сразу вижу, как это сделать для неразрешимости колмогоровской сложности, несмотря на то, что основополагающее доказательство как-то «одинаково». Так:

Является ли неразрешимость колмогоровской сложности быстрым следствием - не требующим дополнительной диагонализации - теоремы Лавре о неподвижной точке?

Джошуа Грохов
источник
2
Я должен сказать, что все, что я когда-либо знал об этой теме, я узнал из этой записи в блоге Андрея Бауэра: math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem
Сашо Николов
1
@MaxNew: Пусть вычислимая функция, вычисленная по некоторым ТМ . Пусть будет следующим ТМ: при пустом вводе он начинает проходить строки по одной за раз, пока не найдет с и выход . Обратите внимание, что для некоторого зависящего только от, Тогда для любого такого, что( подойдет любое достаточно большое ), либо такого (в этом случае ), либо выдает некоторыйM M k x f ( x ) | х | > к х | М к | log 2 ( k ) + c c | М | k k > | М к | k x f C M k x f ( x ) | х | > k M k x CfMMkxf(x)|x|>kx|Mk|log2(k)+cc|M|kk>|Mk|kxfCMkxтакой, что (по построению), но тот факт , что выход следует , что , поэтому . f(x)|x|>kMkxf ( x ) C ( x )C(x)|Mk|<kf(x)C(x)
Джошуа
2
@NealYoung: похоже, но они не совсем отвечают на мой вопрос. Снижение от проблемы остановки означает, что HALT является «источником» невычислимости, а затем использует сокращения. Но (например) доказательство, которое я привел в комментариях выше, показывает, что вы также можете принять K-сложность в качестве «источника невычислимости», но очень похожим доказательством для HALT. Можно ли показать, что подобное аналогичное доказательство действительно в каком-то техническом смысле одинаково ? (В данном случае, показывая, что все они являются примерами теоремы Лаврэра, которая кажется мне более сильной, чем многие виды сокращений.) Это то, что я действительно после.
Джошуа
1
@NealYoung: Да, это обобщает теорему Роджера о неподвижной точке. Но если вы будете думать только о ней как о теореме Роджера, вы упустите суть; Дело в том, что закон Лоувера достаточно общий, чтобы охватить стратегию доказательств из множества различных доказательств, помимо того, что есть у Роджера. Статья Йонофски, о которой идет речь в этом вопросе, предназначена для «без категорий» изложения теоремы Лаврера, дружественной к людям, для которых теория категорий Лаврера может быть пугающей.
Джошуа
3
См. Также cstheory.stackexchange.com/a/2830
Саламон

Ответы:

14

РЕДАКТИРОВАТЬ: Добавление предостережения о том, что теорема Роджера о фиксированной точке не может быть частным случаем Лавр.

Вот доказательство, которое может быть «близким» ... Оно использует теорему Роджера о неподвижной точке вместо теоремы Лаврера. (См. Раздел комментариев ниже для дальнейшего обсуждения.)

Пусть - колмогоровская сложность строки x . K(x)x

Лемма . не вычислимоK .

Доказательство .

  1. Предположим для противоречия, что вычислимо.K

  2. Определите как минимальную длину кодирования любой машины Тьюринга M с L ( M ) = { x } . K(x)ML(M)={x}

  3. Существует константа такая, что | K ( x ) - K ( x ) | c для всех строк x .c|K(x)K(x)|cx

  4. Определим функцию такой , что F ( M ) = М ' , где L ( М ' ) = { х } , такие , что х является минимальной строки таким образом, что К ( х ) > | M | + с . ff(M)=ML(M)={x}xK(x)>|M|+c

  5. Поскольку вычислимо, то и f .Kf

  6. По теореме Роджера с фиксированной точкой , имеет неподвижную точку, то есть, существует машина Тьюринга М 0 такое , что L ( М 0 ) = L ( М ' 0 ) , где M ' 0= F ( М 0) .fM0L(M0)=L(M0)M0=f(M0)

  7. По определению в строке 4 имеем L ( M 0 ) = { x } такое, что K ( x ) > | M 0| + с .fL(M0)={x}K(x)>|M0|+c

  8. Строки 3 и 7 подразумевают , K(x)>|M0|

  9. Но по определению в строке 2 K ( x ) | M 0| , противоречащий строке 8.KK(x)|M0|

Нил Янг
источник
4
Насколько я знаю, теорема Роджера о неподвижной точке не является примером теоремы Лоувера о неподвижной точке. Однако это вариант, потому что в эффективном топосе он звучит следующим образом: если является взаимно оцененной сюръекцией, то A обладает свойством с фиксированной точкой. (Теорема Лавре в эффективном топосе такова: если f : B A B является сюръекцией, то A обладает свойством с фиксированной точкой.)f:NANAf:BABA
Андрей Бауэр
Над моей зарплатой @AndrejBauer - я не знаю теорию категорий. Попробовал прочитать это и ваш ответ здесь . Все еще не понимаю. Можете ли вы сказать мне в своем комментарии выше для теоремы Роджерса, что вы берете для функции (с типом f : N A N ) и что такое A ? Или, может быть, предложить соответствующий учебник? ff:NANA
Нил Янг
4
Слайды 45 и 46 в math.andrej.com/wp-content/uploads/2007/05/syncomp-mfps23.pdf (хорошая новость заключается в том, что теперь у меня есть определенный план и крайний срок для написания обширной статьи о синтетической вычислимости ).
Андрей Бауэр