I think physics (and computer science) is a little more powerful than what you give it credit for. There is some (maybe not a lot, but definitely some) research into alternate physical laws that are plausible & consistent. Complexity theory (the study of the P/NP/EXP/&c. thing) also talks about this in terms of 'oracles': what happens if we assume that we can solve any NP problem in one step (aka an 'NP oracle')? Well, it turns out that you get another level of problems that are 'NP-oracle'-hard. And if you have an 'NP-oracle'-oracle, well, then you get a class of ''NP-oracle'-oracle'-hard problems, which leads us to believe that our conception of computation really is a universal thing. Even if other universes exist with magical computation abilities, they'll still run into problems that are similar to the ones we have now. Or at least that's how I understand this stuff.