In reference to your comments on arithmetic, I'm pretty sure Godel's Incompleteness Theorem states that you -can't- have a fully self-describing mathematical system. But I may be misunderstanding what you're saying there.

Godel created a numbering scheme for statements in a formal system that was strong enough to contain arithmetic. The syntactic rules of the logic could be represented as statements in that logic using only arithmetic operations on the numeric representation of statements. Each statement could also be numbered according to the same scheme, and the system was now self-describing because its definition was in the same language that it operated on. From there it was a matter of encoding the statement Y="There does not exist a sequence of valid derivations in X that results in Y" using the numbering scheme and replacing X and Y where they appear in the statement with the numerical representations of X and Y.

In short, Godel used a self-describing formal system to prove that all formal systems capable of arithmetic were either inconsistent or incomplete. Self-description is not a problem in general, but Godel's construction works at a meta-level above the system itself. From inside the universe we will only have evidence that our natural laws match or do not match the actual rules.