Let’s say I have some function that maps a string of n bits to a string of m bits, and I want to implement it on some computer. Obviously, there are an infinite number of ways to implement it, and some will be more expensive than others, which implies that there is an optimal implementation(for a given computer architecture, of course).

Now, suppose I have an implementation of my function, but it seems to be quite a lot more expensive than it needs to be. Is there any algorithm I could apply to my function to make it cheaper(without blowing up memory requirements to 2**n, that is)? I don’t think that the algorithm necessarily needs to operate on recursively enumerable functions; the function will be limited to looping, basic arithmetic and if statements.

Is what I’m asking for hopeless vague(or just plain hopeless)?

I suppose another way of putting this is:

a) Is there any way I can even approximate the cost of the optimal implementation of a given function that corresponds to my restrictions?

b) How would one go about actually writing a near-optimal implementation?