Искал тут недавно список алгоритмически неразрешимых задач, и наткнулся на список в Википедии. Особенно меня удивила проблема о невозможности построения идеального архиватора. Никак не могу понять, что к чему. Задача: требуется написать программу, которая для любого входного файла напишет минимальную программу, выводящую этот файл. Утверждается, что это невозможно. Однако почему, например, не работает следующий алгоритм:

1) Положим текущим минимумом программу содержащую выходной файл и выводящую его на экран (это всегда возможно)

2) Переберём все программы меньшие данной и найдём минимум (таких программ конечное количество)

Что здеесь не так?

Так же предложенный алгоритм вычисляет Колмогоровскую сложность любой строки, однако, как утверждается, это невозможно.

UPDATE1:

Всё, понял, спасибо всем за ответы. Невозможно выполнить шаг 2, т.к. невозможно перебрать все программы ввиду невозможности определить, завершаться они или нет за конечное время => данный алгоритм не завершиться за конечное время

UPDATE2:

Всё вышеперечисленное относится к идеальным машинам, имеющим неограниченное количество состояний. Однако такие машины физически не реализуемы. Итого некоторые алгоритмически неразрешимые задачи становятся решаемыми в реальном мире. Нет ли примеров таких задач, которые в принципе алгоритмически не разрешимы, но вполне себе решаются в реальном мире (не приближённо, а именно точно). Приветствуются примеры, имеющие суб-экспоненциальную сложность (если таковые имеются).