However for an infinite domain, I strongly suspect it's not possible, due to the fact that it's impossible to tell in general (e.g. it's uncomputable) if two programs compute the same function. This is due to Rice's theorem, and hence ultimately to the Halting problem.
It's possible there may be some kind of constructive proof but I find it unlikely.
So in summary, general superoptimisation is probably impossible.
Domains are almost never truly infinite. You tend to be bound by at least the space of memory even in the brute-force case, and the meaningful domain for any meaningful function (especially one small enough to be optimized intensively) is much less.
Domains are not infinite in practice, but I think it's important to establish the theoretical behaviour and possibilities for the infinite case. They can for example give us a good indication of the 'asymptotic' behaviours of algorithms.
A finite domain isn't the same thing as an infinitely big function.
Ever written a function that takes a list? You've got an infinite domain. (Well, generally in most programming languages not actually infinite, but the upper bound is so large that it might as well be.)
However for an infinite domain, I strongly suspect it's not possible, due to the fact that it's impossible to tell in general (e.g. it's uncomputable) if two programs compute the same function. This is due to Rice's theorem, and hence ultimately to the Halting problem.
It's possible there may be some kind of constructive proof but I find it unlikely.
So in summary, general superoptimisation is probably impossible.