Я ищу доказательство того, что колмогоровская сложность невычислима, используя редукцию из другой невычислимой задачи. Общим доказательством является скорее формализация парадокса Берри, чем сокращение, но должно быть доказательство путем сокращения из чего-то вроде проблемы остановки или проблемы корреспонденции по почте.
источник
Это был забавный вопрос для размышления. Как описано в другом ответе и комментариях ниже, существует редукция Тьюринга от задачи Остановки к вычислению колмогоровской сложности, но, в частности, такого сокращения много-один, по крайней мере, для одного определения «вычисления колмогоровской сложности» не существует.
Давайте формально определим, о чем мы говорим. Пусть обозначает стандартный язык ТМ, которые останавливаются при описании их самих в качестве входных данных. Пусть обозначим .HALT KO {⟨x,k⟩∣x has Kolmogorov complexity exactly k}
Предположим, что путем некоторого сокращения много один. Пусть обозначает функцию, которую вычисляет эта редукция. Рассмотрим изображение под , которое я обозначу .HALT≤KO f:{0,1}∗→{0,1}∗ HALT f f(HALT)
Заметьте, что состоит из строк вида где имеет колмогоровскую сложность ровно . Я утверждаю, что , которые встречаются в не ограничены, поскольку существует только конечное число строк с колмогоровской сложностью ровно , а бесконечно.f(HALT) ⟨x,k⟩ x k k f(HALT) k f(HALT)
Так как рекурсивно перечислим (в некоторых книгах он распознается по Тьюрингу), отсюда следует, что рекурсивно перечислим. В сочетании с тем фактом, что не ограничены, мы можем перечислять пока не найдем некоторый с настолько большим, насколько мы хотим; то есть существует TM который на входе выводит некоторый элемент .HALT f(HALT) k f(HALT) ⟨x,k⟩ k M k ⟨x,k⟩∈f(HALT)
Напишите новый TM который выполняет следующее: сначала вычислитеиспользуя теорему Клини о рекурсии. Запросите с помощью ввода чтобы получить . Выход .M′ |M′| M |M′|+1 ⟨x,|M′|+1⟩∈f(HALT) x
Ясно, что на выходе из есть строка с колмогоровской сложностью не болеено что является противоречием.x M′ |M′| ⟨x,|M′|+1⟩∈f(HALT)
Я полагаю, что вы также можете заменить в задаче «Колмогоровская сложность ровно » на «Колмогоровская сложность не менее » с небольшими изменениями.k k
источник