Minimalizacja programu

Minimalizacja obwodu to problem polegający na zminimalizowaniu rozmiaru danego obwodu. Czy jest coś podobnego do programów ogólnych?

W szczególności moje pytanie brzmi -

Czy istnieją algorytmy minimalizujące liczbę instrukcji dla danego programu? Wiem, że to nierozstrzygalny problem, ale nie szukam rozwiązania, które zwróci coś optymalnego.

Podczas gdy można zastosować wcześniej istniejące transformacje kompilatora, szukam czegoś, w którym nie muszę definiować zestawu bardzo wąskich transformacji i algorytmów, aby je wcześniej wyszukać.

Edycja: Drugim pytaniem, jakie mam, jest to, czy można mieć rachunek dźwiękowy, który jest solidny i kompletny, co pozwala nam badać całą przestrzeń takich semantycznie równoważnych programów, czy też nie jest to możliwe.

Istnieje naiwny algorytm dla programów z wejściami o ograniczonym rozmiarze: wylicz wszystkie programy w kolejności rosnącej długości (lub czasu wykonania, który jest ograniczoną funkcją długości). Jeśli możesz udowodnić, że program jest równoważny oryginałowi, zatrzymaj się; w przeciwnym razie szukaj dalej.

Ten algorytm jest zdrowy. Aby było kompletne, musisz być w stanie udowodnić, że wszystkie odrzucone programy nie są równoważne z oryginałem. Jest to możliwe w modelach maszyn skończonych, o ile istnieje granica wielkości wejściowej.

Należy pamiętać, że gdy czas wykonania programu zależy od danych wejściowych, może nie być optymalnego rozwiązania. Jeśli szukasz np. Granicy najgorszego przypadku, bardzo szybko natrafisz na nierozstrzygalne ekwiwalenty podczas kwantyfikacji wszystkich możliwych niezwiązanych danych wejściowych i na nierozwiązywalne problemy, jeśli dane wejściowe są ograniczone.

Dziesięć lat temu Rajeev Joshi, Greg Nelson i Keith Randall „Denali: ukierunkowany na cel superoptimizer” potrafili znaleźć optymalne programy zawierające około 5 instrukcji maszynowych. Nie spojrzałem na nowsze wyniki.