Since physical states exist in reality, it makes no sense to me that a physical problem is not mathematically decidable.

The only way a problem is mathematically undecidable is when it's malformed (i.e. non-sensical).