Re: "Consider a universal prior based on an arbitrary logical language L, and a device that can decide the truth value of any sentence in that language. Such a device has no finite description in L (according to Tarski's undefinability theorem), so the universal prior based on L would assign it zero probability."

It would never see the infinite description with the 0 probability, though - not enough space-time.

The evidence of the Oracle that the agent would get to see would be in the form of finite sensory inputs - and those would not be assigned zero probability. So: it could update on that evidence just fine - with no problems.

If the agent sees a tiny box with an Oracle inside it, that is just more finite sense-data about the state of the universe to update on - no problem - and no silly p=0 for an empirical observation.