Об оптимизации
Dec. 23rd, 2010 03:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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)
Доказательство: для любой программы без побочных эффектов, которая не завершается (зацикливается), самое короткое представление известно - [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)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-12-23 09:18 am (UTC)no subject
Date: 2010-12-23 12:01 pm (UTC)в конец программы добавляем "удалить все результаты, вывести 0".
каноническое представление такой программы известно.
no subject
Date: 2010-12-23 06:38 pm (UTC)no subject
Date: 2010-12-23 08:23 pm (UTC)Из доказательства №1 следует что компилятор не сможет отличить останавливается ли программа. Про размер или скорость для тех что завершаются ничего сказать нельзя.
и №2 просто пытается поставить проблему останова на службу для обеспечения работой авторов компиляторов. То есть оно не дает ничего кроме шутки.
вероятно поэтому комитеты си и си++ дружно решили разрешить компилятору предполагать что программы завершаются и выбрасывать бесконечные циклы. Еще не приняли но уже почти. Под Аппеля копают xD
no subject
Date: 2010-12-27 08:13 pm (UTC)