Об оптимизации

[thedeemon]

Теорема 1: невозможно построить компилятор, который любую программу оптимизировал бы до самого короткого (или быстрого) ее представления.
Доказательство: для любой программы без побочных эффектов, которая не завершается (зацикливается), самое короткое представление известно - [L: goto L]. Если бы идеальный оптимизирующий компилятор существовал, мы могли бы с его помощью решить проблему остановки, сравнивая его выход с этим коротким циклом. Что противоречит уже доказанной неразрешимости проблемы остановки.

Теорема 2: для всякого оптимизирующего компилятора можно сделать компилятор еще круче.
Доказательство: пусть дан компилятор А, и известно, что для некоторой незавершающейся программы Р1 его выход А(Р1) отличен от [L: goto L], такая программа всегда существует в силу теоремы 1. Тогда построим компилятор
B(P) = if P == P1 then [L: goto L] else A(P)
Он гарантированно лучше А, ч.т.д.

Теорема 2 известна под именем full employment theorem for compiler writers. :)

(Евангелие от Аппеля, глава 17)

Comments

[n0mad-0.livejournal.com]

а если в Т1 выколоть незавершающиеся программы и рассматривать только завершающиеся?

[mr-aleph.livejournal.com]

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