(Response to March 25th post) That's right, just looking at the very nature of measuring a single observable is very fundamental to undecidability. My comparison mentioned above is focused on complementary observables. In that analysis the phenomenological experience of nature involved in measuring one observable would have as its underpinning some self-referential operation of the other observable - this is manifested physically in the specific measuring action (such as direction of the magnetic field, the way the detector interacts, etc.). A bit subtle is the linking between the two observables - the SR operation relates to one observable in the act of measuring the other.
Regarding a single observable, consider that every observable has a complementary conceptual observable out there. So the |+> and |-> oscillating superposition in some way perhaps corresponds to another observable with an already decided value. If a measurement specific to this 'another observable' were made, it would not affect the already oscillating superposition of |+> and |->. Then, physically doing what is necessary to measure the|+> and |-> system (i.e. to determine if in the excited or unexcited state) would effectively be a SR operation on that 'another observable.' The undecidability of |+> and |-> is now swapped for undecidability in this 'another' domain. This is the same reasoning applied to pairs of observables already known to be complementary, like Sx and Sz. This again shows not everything can be decided together.
Now, one might say this was still a physical undecidability; if so then by our new measurement we physically transferred the undecidability so to speak. But what did we really do? We changed the nature of our measuring environment, that is we sought to explain the system differently by conceptually distinguishing a different observable. Remember that changing a mathematical representation requires a change in physical explanation. "Change in physical explanation" is more vague than "change a mathematical representation" so more is needed to state this conversely: By distinguishing out a different observable, we're changing how we physically explain a system. If we seek to explain by distinguishing an observable that can't be described in a particular mathematical basis, then we must represent by a different basis. But what if we just try to change the representation to begin with? This can be done symbolically. If we have a measurement in Sx (let's say it's UP) and now we wish to represent that using a basis of (X up, X down), well we can't - that's mathematically undecidable as you brought out above. For example, (X up + X down)/в€љ2 does not give you a decided measurement of Sx. It was an attempt to represent it with respect to itself, and is thus self-referential. This mathematical self-referential operation is undecidable, but can be used to describe a decided value of a new concept Sz whose value would be UP. When physically manifested this changes the paradigm of explanation - it destroys any measured value of Sx and instead produces a new decided observable Sz.
That not everything can be decided together squashes Hilbert's attempts as we noted above. (Maybe the Halting Program can be reformulated with the basis B and states T(n) as the inputs). That not everything can be explained together reflects complementarity. That each of these leads to each other shows the equivalence of mathematical incompleteness to physical uncertainty.