Czy istnieją w pełni optymalizujące kompilatory do kończenia programów?

W książce Andrew W. Appela, Modern Compiler Implementation in ML , mówi w rozdziale 17, że teoria obliczalności pokazuje, że zawsze będzie możliwe wynalezienie nowych transformacji optymalizacyjnych i udowadnia, że w pełni optymalizujący kompilator rozwiąże problem zatrzymania: Program Q, który nie wytwarza mocy wyjściowej i nigdy nie zatrzymuje się, można łatwo zastąpić jego optymalną reprezentacją, Opt (Q) , oznaczającą „L: goto L”. Zatem w pełni optymalizujący kompilator może rozwiązać problem zatrzymania.

Moje pytanie brzmi zatem: czy istnieje w pełni optymalizujący kompilator do zamykania programów? Moje jedyne przemyślenia są następujące: Mimo że program ma zagwarantowane zakończenie, wciąż może być arbitralnie złożony, a dla każdego konkretnego kompilatora optymalizującego C można by skonstruować program, który przyjmuje C jako dane wejściowe i w jakiś sposób wytwarza gorszy program jako jakaś skrzynka narożna.

Również Jakie są implikacje ograniczając się do zakończenia programów?

computability compilers program-optimization

— Simon „Reinstate Monica” Shine
źródło

Trudno jest nawet znaleźć optymalną sekwencję instrukcji dla pojedynczego bloku kodu bez żadnego przepływu sterującego. Superoptimization artykuł na Wikipedii daje dobre Intro (z cytatów.)

— wędrując Logic

Artykuł w Wikipedii wspomina, że superoptymalizacja analizuje sekwencje instrukcji bez pętli. Przypuszczam, że brak pętli to kolejny sposób na powiedzenie, że się kończy. Po krótkim spojrzeniu na dostępne referencje wydaje się to możliwe, ale niezwykle kosztowne.

— Simon „Reinstate Monica” Shine

Co oznacza tutaj „optymalizacja”? Mniejszy czas działania? Jeśli tak, to które: najgorszy przypadek, średni przypadek, każdy przypadek, jakiś przypadek, ...?

— Raphael

Zakładam, że jesteś zainteresowany optymalizacją środowiska uruchomieniowego. Jak napisałem w moim komentarzu, nie określa to w wystarczającym stopniu celu: czy optymalizacja skraca czas działania dla dowolnego wejścia, każdego wejścia, wszystkich danych najgorszych, a nawet średnio ?

Pokażę, że wszystkie są niemożliwe. Dowód obejmuje optymalizację długości programu.

Pamiętaj, że następującego problemu nie można obliczyć:

Biorąc pod uwagę bezkontekstową gramatykę z terminalnym alfabetem , zdecyduj, czy . $G$ $\Sigma$ $\mathcal{L}(G) = \Sigma^*$

Zauważ też, że biorąc pod uwagę bezkontekstową gramatykę , możemy na przykład zakodować algorytm CYK dla tej jednej gramatyki; ten algorytm przez . Zauważamy, że kończy się dla wszystkich danych wejściowych (od ). $G$ $\mathrm{CYK}_G$ $\mathrm{CYK}_G$ $\Sigma^*$

Załóżmy teraz, że nie jest optymalizator , który podawany jest zawsze zakończenia algorytm , wysyła wynik algorytmu równoważne który jest optymalny w odniesieniu do wykonywania. Wyraźnie, $\operatorname{Opt}$ $A$

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

i w ten sposób skonstruowaliśmy czynnik rozstrzygający dla problemu nieobliczalnego, co jest sprzeczne z założeniem.

— Raphael
źródło

Dziękuję za ten argument. Kilka pytań wyjaśniających: Co to jest ? Sądzę jest generowany przez język gramatyki .

Σ *

$\Sigma*$

L (G)

$\mathcal{L}(G)$

G

$G$

— Simon „Reinstate Monica” Shine

@ Simon: to zestaw wszystkich słów. Raphael: Niezły dowód. W rzeczywistości nie potrzebujesz gramatyk bezkontekstowych; zamiast tego, mając maszynę Turinga , możesz utworzyć program który symuluje kroki dla i zwraca true, jeśli maszyna osiągnie stan akceptacji. Wtedy to iff nie zatrzymuje się.

Σ^{*}

$\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,