Искал тут недавно список алгоритмически неразрешимых задач, и наткнулся на список в Википедии. Особенно меня удивила проблема о невозможности построения идеального архиватора. Никак не могу понять, что к чему. Задача: требуется написать программу, которая для любого входного файла напишет минимальную программу, выводящую этот файл. Утверждается, что это невозможно. Однако почему, например, не работает следующий алгоритм:
1) Положим текущим минимумом программу содержащую выходной файл и выводящую его на экран (это всегда возможно)
2) Переберём все программы меньшие данной и найдём минимум (таких программ конечное количество)
Что здеесь не так?
Так же предложенный алгоритм вычисляет Колмогоровскую сложность любой строки, однако, как утверждается, это невозможно.
UPDATE1:
Всё, понял, спасибо всем за ответы. Невозможно выполнить шаг 2, т.к. невозможно перебрать все программы ввиду невозможности определить, завершаться они или нет за конечное время => данный алгоритм не завершиться за конечное время
UPDATE2:
Всё вышеперечисленное относится к идеальным машинам, имеющим неограниченное количество состояний. Однако такие машины физически не реализуемы. Итого некоторые алгоритмически неразрешимые задачи становятся решаемыми в реальном мире. Нет ли примеров таких задач, которые в принципе алгоритмически не разрешимы, но вполне себе решаются в реальном мире (не приближённо, а именно точно). Приветствуются примеры, имеющие суб-экспоненциальную сложность (если таковые имеются).
А как сделать шаг 2?
Имеем абстрактную вычислительную машину. Результат работы алгоритма — программа, выводящая введённую строку. Изначально за минимальный размер примем саму входную строку и код выводящий её на экран. Он имеет размер N. Теперь в соответствии с синтаксисом машины будем перебирать все возможные программы размер которых меньше N. Просто тупо перебираем все возможные команды. Это долго, но это делается за конечное время. Следовательно, этот алгоритм работает.
А почему программ, меньших данной, конечное число? Размер алфавита чем-то ограничен?
Да, размер алфавита всегда в этой теории ограничен для простоты 2)
Вы не можете проверить выводит программа результат или нет.
Проблема останова(ки)
По описанию данного алгоритма она всегда выдаст результат за конечное, пусть и долгое время, и не зациклиться
Вы перебираете программы. И вот остановятся ли они, вы не знаете. Если все они остановятся, то и ваша остановится. С этим я не спорю
допустим есть программа while(1){} она очень короткая, пока она не остановится вы не сможете сказать она ли ответ или не она.
На самом деле, не все так просто. Вот, например, одна из загвоздок, которая делает описанный в посте подход неприменимым. Первой же алгоритмически неразришимой задачей по приведенной ссылке является проблема остановки. А именно, утверждается, что по заданной программе и входным данным, невозможно за конечное время определить, завершится ли заданная программа на этих входных данных. Так вот, если мы будем перебирать все корректные программы фиксированной длины, то мы даже не сможем определить, какие из них завершатся, а какие — зациклятся.
Проблемма в том, что некоторые такие программы могут работать бесконечно долго и вы не сможете понять какая из них остановится и когда выдать ответ.
Жду ответов и комментариев по последнему вопросу.
Колмогоровская сложность с ограничением на память и время вполне себе вычислимая сущность )) только чтобы её промоделировать нужна машинка с ГОРАЗДО большей памятью. Непонятно что вы имеете ввиду какие задачи вы хотите...
Я слабо понимаю как вы хотите уйти от математического понятия ограничев(!) себя реальной жизнью и при этом научиться что-то решать, что до этого не могли.
Ну если в общем случае решения нет, то почему бы не поискать эффективного решения в частном?
Я абсолютно не профессионал в этом вопросе, но:
Например, исходный файл, в виде стоки битов выглядит так: 010111001010101
1) 01[2]1110010[3]1 2) A[2]1110A0[3]1
1) A[2]1110A0[3]1 2) A[2]Б10A0[3]1
1) -//- 2) A[2]БСA0[3]1
1) -//- 2) A[2]ДА0[3]1
1) -//- 2) A[2]Е0[3]1
1) -//- 2) A[2]Ж[3]1
При длине стремящейся к бесконечности будем получать хорошие результаты. Ну как расшифровывать, вроде бы очевидно.
Если Вы не профессионал в вопросе, не надо пытаться делать категоричные выводы.
Контрпример к Вашему алгоритму — сжатие десятичного представления числа Фибоначчи F100000. Вот короткая программа на Java, которая выведет то, что нам нужно, на консоль:
Она не претендует на оптимальность, но при этом она явно занимает меньшее количество байт, нежели сжатая Вашим алгоритмом строка.
Да, давно не было доказательств теоремы Ферма, которые бы влезли на поля...