I'm not actually sure that computable physical theories are actually capable of encompassing basic arithmetic. You can certainly make machines within them which return basic arithmetic results for certain bounded sets of input, but thats not the same thing as possessing the sort of self-reference structure that leads to Godel incompleteness.

Classical physics isn't a correct theory of our universe, but it does describe a set of universes that are completely computable. Given initial conditions, their future states for all times are strictly defined and there's an algorithm to obtain them. You can build a computer in such universes. But mathematical truths aren't physical realities in those universes, so even if you can talk about mathematics, you can't actually build 'mathematics itself' as a physical thing within those universes such that, e.g., the truth values of arbitrary statements always correspond to some measurable physical state.