![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Об оптимизации
Dec. 23rd, 2010 03:01 pmТеорема 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)
Доказательство: для любой программы без побочных эффектов, которая не завершается (зацикливается), самое короткое представление известно - [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)
![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif){kind=small}
