Dear Michael,
you've provided a well-argued essay that takes the abstract notions of 'austere' mathematical Platonic domains and confronts them with the hands-on reality of the actual world. Do the issues noted by Gödel, Turing, and others survive the confrontation with a messy, noisy world of increasing entropy and finite resources?
You answer in the negative---and in the way you frame the debate, I can only agree: there is no device that could be built that actually realizes the necessary preconditions for undecidability to apply. Even the simplest possible systems that could hope to achieve computational universality eventually fall prey to the loss of energy to the environment, and to the degradation of their signal-bearing vehicles.
Sure, one could quibble at certain points. For instance, the famous result by Cubitt et al., demonstrating that whether a certain system has a gapped ground state is an undecidable question, essentially only applies to systems with an infinite number of degrees of freedom---and while such systems do exist in quantum field theory, arguments from e. g. the Bekenstein bound may be taken to suggest that an ultimate theory of nature ought to be finitary in this sense.
Likewise, one can show that the question of whether a certain output port in a chain of iterated quantum measurement (Stern-Gerlach type) experiments stays dark, is undecidable. But neither of these really demonstrates an exploitable source of undecidability.
But I don't think that the failure of concrete systems capable of universal computation in a realistic context to exist entails the inapplicability of Gödelian reasoning in a physical setting.
Consider randomness. Famously, no computational process can produce genuine randomness---not indefinitely, at least. Any given formal system can only approximate a random number to a finite degree; the digits of the number beyond that threshold correspond to undecidable propositions. Hence, as Feynman put it, "it is impossible to represent the results of
quantum mechanics with a classical universal device". To the extent that there is randomness, undecidability is relevant to physical reality.
Fine, one might say. We only ever make finite observations; it's good enough to use some pseudorandomness for our purposes. But then, it turns out, one can use entangled systems to send faster-than-light signals, in conflict with special relativity; hence, all such models must be noncomputable.
More generally, I think that even though undecidability may not apply on the level of concrete devices, this doesn't entail that it can't have no role to play in the formulation of laws themselves.
One typical argument one encounters is that we only ever make a finite set of observations, hence, collect finite data, which can be produced by a finitary system, such as a finite state automaton. That's of course true. But such a model would, effectively, be equivalent to a computer program that just outputs that data, without significantly compressing it; hence, if would yield poor predictive power.
But then, how could one have predictive power if, for instance, the data is due to a non-computable process? Well, any such process can be decomposed into a finite algorithm and a source of randomness---say, a string of random digits. An observer faced with (finite) observations of noncomputable data could then figure out the algorithmic part, and thus, explain their observations in terms of some algorithmic process interspersed with random events---which is, of course, exactly what we see.
So, in the end, I think that there's a window for the applicability of undecidability to natural law that your arguments leave open---and, as is probably no surprise given my own essay, I believe that this is what actually is realized in nature.
Still, I wish you the best of luck in the contest!
Cheers
Jochen
