# Program Minimization

Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs?

In particular my question is -

Do there exist algorithms to minimize the # of instructions for a given program. I know it's an undecidable problem but I'm not looking for a solution that returns something optimal.

While one can apply preexisting compiler transformations to accomplish this, I'm looking for something where I don't have to define a set of very narrow transformations and algorithms to search for them beforehand.

Edit: The other question I have is whether one can have a calculus that is sound and complete that allows us to explore the whole space of such semantically equivalent programs or is that not possible.

• The answer to your other question depends on your definition of "a calculus". $\:$ The fact that HALT is not in coRE makes the answer "no" for most such definitions. $\;\;\;\;$
– user6973
Mar 10 '14 at 22:23
• the two fields are related in that another approach is to convert the programs to the family of circuits for varying input sizes $f_n$
– vzn
Mar 11 '14 at 20:16