Существуют ли полностью оптимизирующие компиляторы для завершающих программ?

В книге Эндрю У. Аппеля « Реализация современного компилятора в ML» он говорит в главе 17, что теория вычислимости показывает, что всегда можно изобрести новые оптимизирующие преобразования, и продолжает доказывать, что полностью оптимизирующий компилятор решит проблему остановки: Программа Q, который не производит никакого вывода и никогда не останавливается, может быть легко заменен его оптимальным представлением, Opt (Q) , являющимся "L: goto L". Таким образом, полностью оптимизирующий компилятор может решить проблему остановки.

Поэтому мой вопрос таков: существует ли полностью оптимизирующий компилятор для завершения программ? Мои единственные мысли следующие: даже если программа гарантированно завершает работу, она все равно может быть сколь угодно сложной, и для любого конкретного оптимизирующего компилятора C можно было бы построить программу, которая принимает C в качестве входных данных и каким-то образом создает худшую программу как какой-то угловой чехол.

Кроме того, каковы последствия ограничения нас на прекращение программ?

computability compilers program-optimization Симон 'Восстанови Монику' Блеск
источник

Трудно даже найти оптимальную последовательность команд для одного блока кода без какого-либо потока управления. Superoptimization статья в Википедии дает хорошее введение (с цитатами.)

блуждающих Logic

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

Саймон 'Восстанови Монику' Сияние

Что означает «оптимизировать» здесь? Меньшее время выполнения? Если да, то какие: наихудший случай, средний случай, каждый случай, какой-то случай, ...?

Рафаэль

Ответы:

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

Я покажу, что все они невозможны. Доказательство распространяется на оптимизацию длины программы.

Напомним, что следующая проблема не вычислима:

Учитывая неконтекстную грамматику с терминальным алфавитом , решите, будет ли . $G$ $\Sigma$ $\mathcal{L}(G) = \Sigma^*$

Кроме того, обратите внимание, что с учетом неконтекстной грамматики мы можем жестко закодировать, скажем, алгоритм CYK для этой одной грамматики; Обозначим этот алгоритм на . Заметим, что заканчивается для всех входов (из ). $G$ $\mathrm{CYK}_G$ $\mathrm{CYK}_G$ $\Sigma^*$

Теперь предположим, что существует оптимизатор который при всегда завершающемся алгоритме выводит алгоритм, эквивалентный результату, который является оптимальным по времени выполнения. Очевидно, что $\operatorname{Opt}$ $A$

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'} \iff \mathcal{L}(G) = \Sigma^*$

и таким образом мы построили решатель для невычислимой задачи, противоречащей предположению.

Рафаэль
источник

Σ *

$\Sigma*$

L (G)

$\mathcal{L}(G)$

G

$G$

Σ^{*}

$\Sigma^{\ast}$

M

$M$

P_{M} (i)

$\mathrm{P}_M(i)$

M

$M$

i

$i$

OPT (P_{M})

$\operatorname{OPT}(\mathrm{P}_M)$

' r e t u r n f a l s e;'

$\text{'}\mathtt{return\ false;}\text{'}$

M

$M$

sdcvvc