http://en.wikipedia.org/wiki/Noether%27s_theorem
"...every continuous symmetry of a physical theory has an associated conserved quantity; if the theory's symmetry is time invariance then the conserved quantity is called "energy" ...".
> In the theory we present here, the status of information in physics is analogous to that of (say) energy: given the laws of motion of physical objects, neither the concept of energy nor the conservation law for the energy-momentum tensor are necessary for making any prediction from initial data, yet our understanding of the physical world would be radically incomplete without them. The conservation law explains some aspects of motion as consequences of a deeper regularity in nature – which is why we expect as-yet-undiscovered laws of motion to conserve the energy-momentum tensor too; but we don’t expect to derive new laws of motion from it. It is a principle – a law of physics that constrains other laws rather than the behaviour of physical objects directly.
I think it's folly to try to differentiate a "law" from a "principle". That said I'm taking his words out of context. He's saying that "information" is something akin to "energy". Ok, but after the hand-waving there is nothing left.
Does he say something more interesting? For example, we've explored many truths about "computation" (e.g. Turing's Halting Problem && Godel's Incompleteness Theorem) that so far have only been discussed in the abstract. But to weave computation/information onto physics raises questions of how these truths we've held in the abstract may also correspond to laws in the physical. That is, it doesn't help us derive new laws of physics (in other words, our laws of physics is always incomplete), but constrains what can be explained by laws (which by definition must be consistent).
TLDR; I agree that information doesn't exist in the abstract but is tied to our physical reality. I think that our inability to find a complete set of laws of the physical universe is intimately related to HP and GIT. I wonder if he gets into it.
Imho "not [...] a priori" is not the same as a simple "not".