Stelling betreffende eeuwige werkgelegenheid voor compilerbouwers

Van Wikipedia

De stelling betreffende eeuwige werkgelegenheid voor compilerbouwers stelt dat gegeven een compiler A, er een compiler B bestaat die betere code genereert. Omdat het altijd mogelijk zal blijven compilers te verbeteren, zouden compilerbouwers hierdoor altijd werk hebben.

[bewerk] Bewijs

In de informatica is bekend dat het beslissingsprobleem onberekenbaar is, dat wil zeggen, er bestaat geen programma dat kan bepalen of een ander programma stopt.

Het kortste programma dat niet stopt, in bijvoorbeeld Pascal, is:

program stopt_niet;

begin
  repeat
  until false;
end.

Een perfecte compiler zou dus een programma dat niet stopt moeten kunnen reduceren tot het bovenstaande programma. Maar in dat geval zouden we het beslissingsprobleem opgelost hebben. Immers, we zouden onze perfecte compiler op een programma kunnen loslaten, en kijken of de compiler dit weet te reduceren tot bovenstaand programma.

Maar omdat het beslissingsprobleem niet oplosbaar is, kan een perfecte compiler niet bestaan en bestaat dus voor iedere compiler een betere compiler.