Hi Lawrence,
this is a very intriguing essay that touches on a lot of things that I have dimly glimpsed in my own thinking. In particular, the issue of how undecidability relates to physics is something that is intermittently on my mind. There's been a recurring trend to look for undecidability as somehow related to the measurement problem, or other quantum mechanical weirdness, starting with maybe Zwick in 1978, and continued by people such as Mittelstaedt or Thomas Breuer (who uses diagonal arguments to establish the impossibility of perfect self-measurement in theories assumed to be universally valid, that is, apply to observer as well as observed). A relatively recent development is the idea that the randomness of quantum measurement outcomes is related to the undecidability of the outcome from axioms encoded in the state preparation, as developed by Paterek et al. There's also interesting work by Karl Svozil, Christian Calude, and others, in investigating quantum randomness and uncertainty from the point of view of Chaitin's algorithmic information theory.
All of which is just to say that a lot of people have seen some common ground here, while apparently nobody has been able to find a rigorous formulation. Your take on the issue is a new one to me: as far as I understood, you seem to be saying that independent axioms may be repealed in order to allow greater mathematical freedom, citing the case of abandoning the parallel postulate in order to lead in a profitable way to new formulations of geometry. But of course, in any theory, all axioms are logically independent of one another, no? Otherwise, if any axiom can be derived from the other axioms, you can just strike it out, and you'll be left with the same theory. This was what drove the attempts to derive the parallel postulate from the other axioms: it was seen as a blemish on the theory, and it was hoped that the theory would hold up unchanged without it. The construction of geometries inequivalent to Euclid's by Lobachevsky and others ultimately was what killed this hope. (And besides, isn't Euclidean geometry decidable anyway?)
So the parallel postulate ultimately isn't derivable from the theory in the same sense that, say, the existence of the square root of -1 isn't derivable from the field axioms: the incompleteness here is in a sense trivial, and different from the Gödelian case in the sense that one probably wouldn't want to insist that the field axioms are complete in the sense that they derive every true position they can express. So it seems to me that there's a difference between the independence of the parallel postulate and the independence of, say, the continumm hypothesis from Zermelo-Fraenkel.
Also, even though there are undecidable propositions about any sufficiently complex system (any system capable of universal computation), this does not imply any 'uncertainty' about the fundamental laws (though I'm not sure if you're arguing for that): take, for instance, a universal cellular automaton such as the Game of Life. It's 'fundamental laws' are simple enough, and can be completely specified without any problem; nevertheless, there exist undecidable propositions, such as whether or not a specific configuration will ever turn up. But of course, GoL can be simulated on a computer; so the mere existence of undecidability does not imply anything about the uncomputability of physical evolution. So this does not put the hypothesis of the universe being, in some sense, a 'giant computer' to rest: in fact, I would rather consider it evidence in its favour, since as I said, every universal system gives rise to undecidable propositions.
But I'm not quite sure if I'm not arguing past your points; I need to re-read your essay in some calmer moment, I think.