Минимизация программы

Минимизация схемы - это проблема минимизации размера данной схемы. Есть ли что-нибудь подобное для общих программ?

В частности, мой вопрос -

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

Хотя для этого можно применить уже существующие преобразования компилятора, я ищу что-то, где мне не нужно определять набор очень узких преобразований и алгоритмов для их предварительного поиска.

Редактировать: Другой вопрос, который у меня есть, заключается в том, можно ли получить исчисление, которое является надежным и полным, что позволяет нам исследовать все пространство таких семантически эквивалентных программ, или это невозможно.

Существует наивный алгоритм для программ с входными данными ограниченного размера: перечислять все программы в порядке увеличения длины (или времени выполнения, которое является ограниченной функцией длины). Если вы можете доказать, что программа эквивалентна оригиналу, остановитесь; в противном случае продолжайте искать.

Этот алгоритм является здравым. Для того чтобы он был завершен, вы должны быть в состоянии доказать, что все отклоненные программы не эквивалентны оригиналу. Это возможно в конечных моделях машин, если у вас есть ограничение на размер ввода.

Обратите внимание, что, когда время выполнения программы зависит от ввода, может не быть оптимального решения. Если вы ищете, например, границу для наихудшего случая, вы очень быстро столкнетесь с неразрешимыми эквивалентами, когда будете количественно определять все возможные неограниченные входы, и с неразрешимыми проблемами, если входы ограничены.

Десять лет назад Раджив Джоши, Грег Нельсон и Кит Рэндалл «Денали: супероптимизатор, ориентированный на достижение целей», смогли найти оптимальные программы из 5 машинных инструкций. Я не смотрел на более свежие результаты.