I define information as the ability to make information, which means selecting from a low probability portion of a distribution. One precise description of this is:
1. You have a problem domain P to which the No Free Lunch Theorem applies, at least approximately. Thus, there are hard bounds on how well one algorithm can do compared to any other according to some metric.
2. Information is produced when an agent can perform significantly better than is algorithmically possible. One such metric is the compressibility of its search history.
Why is this my definition? Well, it is linked to our intuitive notion of learning and intelligence. As informally described by Hofstadter, it is an inherent ability to "step outside of the system." This means, at some time t I am behaving according to some rule set r, but at time t+c I understand the rule set and can reason about r instead of just being subject to r.
One specific result of being able to reason about a rule set is that I can take some well formed sentence, realize it can't be generated by the rule set, and use a simpler rule set to generate it. When framed in terms of Kolmogrov complexity, I'm exhibiting a general compression capability, which implies a general (though not total) capability to solve the halting problem.
Since a problem domain with structure can be compressed, this relates to my first example in that if an agent has a generally much more compressible history than mathematically expected in a (almost) No Free Lunch domain, it is exhibiting the ability to step outside of its environment's rules, reason about them, and thus compress them.
So, you can see that my definition of intelligence as the ability to create information specifies an unambiguous and measurable capability, which also happens to specify something algorithms are mathematically incapable of doing. Thus, I've have both defined intelligence and disproven the logical possibility of such an AI in one fell swoop.
BTW, this is not an original thought of mine. It is a direct result of intelligent design theory, the progeny of the absolutely brilliant William Dembski.