Without more context for your question, it is impossible to say, but one interpretation is that you may simply be asking about Turing degrees. A set A of natural numbers is a lower bound for the computational complexity of another set B if the characteristic function of A is computable from B, meaning that a Turing machine with oracle B can compute A. If A is itself non-computable, then this shows that B is also non-computable. In practice, this is how many noncomputability results are proved: one has a set B, and proves that it is undecidable by showing that the halting problem reduces to it.
The hierarchy of Turing degrees can be thought of as informational theoretic in nature. If A reduces to B, then B has at least as much information as A.
But you may have a more engineering purpose in mind, or an idea more connected directly with the issues in information theory, in which case this answer is not what you want.