If the set of nontrivial programs is infinite, the situation is more complex, because an instruction set as normally defined is finite. Also, you can't equally weight every program from an infinite set, so you need some kind of weighting function among the programs. Which instruction set is ideal for encoding this infinite set of programs depends almost entirely on what that weighting function is. In fact, you can usually derive the optimal instruction set directly from the weighting function. Which is to say, when you design the weighting function, you are more or less designing the instruction set.
As retrac points out, it comes down to a question of tradeoffs. There's no objectively optimal answer to which tradeoffs you should prefer.
I took some notes some years ago on the subject of dense instruction sets, optimized for the number of bits to encode programs rather than the number of instructions; perhaps you will find them of interest: https://dercuano.github.io/notes/tiny-interpreters-for-micro...