Доказательство сложности Колмогорова неисчислимо, используя сокращения

9

Я ищу доказательство того, что колмогоровская сложность невычислима, используя редукцию из другой невычислимой задачи. Общим доказательством является скорее формализация парадокса Берри, чем сокращение, но должно быть доказательство путем сокращения из чего-то вроде проблемы остановки или проблемы корреспонденции по почте.

Кришна Чиккала
источник

Ответы:

11

Вы можете найти два разных доказательства в:

Грегори Дж. Чайтин, Асат Арсланов, Кристиан Калуде: Сложность размера программы вычисляет проблему остановки. Бюллетень EATCS 57 (1995)

В Ли, Мин, Витаньи, Пол MB; Введение в колмогоровскую сложность и ее приложения представлены в качестве упражнения (с подсказкой о том, как ее решить, что зачислено П. Гачу В. Гасархом в личном сообщении 13 февраля 1992 г.).

** Я решил опубликовать расширенную версию этого в своем блоге .

Марцио де Биаси
источник
1
Кроме того, доказательство Чейтина (в этой ссылке) показывает, что запросы оракула могут выполняться параллельно.
Являются ли эти доказательства действительно редукционными преобразованиями (один к одному (или) один ко многим)? Я запутался !! Пожалуйста, помогите мне
Кришна Чиккала
@KrishnaChikkala: первое, безусловно, сокращение Тьюринга . Я обнаружил, что это не так ясно, поэтому я решил опубликовать расширенную версию этого в своем блоге . Если вы хотите взглянуть на это (и скажите мне по электронной почте, если вы думаете, что это может быть улучшено). Также обратите внимание, что сокращения Тьюринга отличаются от многих сокращений (которые являются «более сильными» сокращениями); действительно, ответ Джо Бебеля доказывает, что такого сокращения не может быть.
Марцио Де Биаси
7

Это был забавный вопрос для размышления. Как описано в другом ответе и комментариях ниже, существует редукция Тьюринга от задачи Остановки к вычислению колмогоровской сложности, но, в частности, такого сокращения много-один, по крайней мере, для одного определения «вычисления колмогоровской сложности» не существует.

Давайте формально определим, о чем мы говорим. Пусть обозначает стандартный язык ТМ, которые останавливаются при описании их самих в качестве входных данных. Пусть обозначим .HALTKO{x,kx has Kolmogorov complexity exactly k}

Предположим, что путем некоторого сокращения много один. Пусть обозначает функцию, которую вычисляет эта редукция. Рассмотрим изображение под , которое я обозначу .HALTKOf:{0,1}{0,1}HALTff(HALT)

Заметьте, что состоит из строк вида где имеет колмогоровскую сложность ровно . Я утверждаю, что , которые встречаются в не ограничены, поскольку существует только конечное число строк с колмогоровской сложностью ровно , а бесконечно.f(HALT)x,kxkkf(HALT)kf(HALT)

Так как рекурсивно перечислим (в некоторых книгах он распознается по Тьюрингу), отсюда следует, что рекурсивно перечислим. В сочетании с тем фактом, что не ограничены, мы можем перечислять пока не найдем некоторый с настолько большим, насколько мы хотим; то есть существует TM который на входе выводит некоторый элемент .HALTf(HALT)kf(HALT)x,kkMkx,kf(HALT)

Напишите новый TM который выполняет следующее: сначала вычислитеиспользуя теорему Клини о рекурсии. Запросите с помощью ввода чтобы получить . Выход .M|M|M|M|+1x,|M|+1f(HALT)x

Ясно, что на выходе из есть строка с колмогоровской сложностью не болеено что является противоречием.xM|M|x,|M|+1f(HALT)

Я полагаю, что вы также можете заменить в задаче «Колмогоровская сложность ровно » на «Колмогоровская сложность не менее » с небольшими изменениями.kk

Джо Бебель
источник
1
Но как насчет сокращения Тьюринга?
Сашо Николов
Позвольте мне выбросить эту идею в комментарии, потому что я не продумал идею. Пусть проблемы решения будет то же самое , но сокращение теперь уменьшение Тьюринга . Рассмотрим множество всех , что в существует некоторая TM, которая заставляет запросить оракула на входе . Я утверждаю, что имеет такое же неограниченное свойство (это нужно обосновать немного больше, чем я заявляю), и можно использовать для построения такого неограниченного , что всегда является противоречием. RSx,kKOHALTRKOx,kKOSkRx,k
Джо Бебель
На самом деле я убираю, что можно использовать таким образом. Это не так ясно в контексте сокращения Тьюринга. R
Джо Бебель
3
В нескольких местах утверждается, что колмогоровская сложность является тьюринговской эквивалентностью проблемы Остановки, например, заметки Милтерсена daimi.au.dk/~bromille/DC05/Kolmogorov.pdf . Если это правда, должно быть сокращение Тьюринга. Кстати, сведение Тьюринга от колмогоровской сложности к проблеме остановки легко и дает другое доказательство того, что остановка неразрешима.
Сашо Николов
HALTTKO следует из аргументов, приведенных в ссылке в другом ответе. На самом деле, поскольку другая редукция (почти) тривиальна, мы имеем . HALTTKO