No, you can prove things hold in the abstract mathematically, don't need to resort to physical systems.
> if our universe is undecidable
My point is, there would be no way to empirically test this; and therefore, it would make no observable difference, there would be no way to exploit/utilise such effects, etc.
In essence: there's no way to tell the difference between a real halting oracle (which would imply an undecidable universe), versus a computable approximation which just-so-happens to be more powerful/sophisticated than the approximations we compare it against.
Sure, we can prove that some abstract systems are undecidable and that others aren't. Yet that distinction is inherently unfalsifiable, and hence physically "useless".