Right, right. This is what I was trying to get at.
Are there any mathematicians/physicists who've tried to formalize "a universe" rather than "the universe" who spring to mind?
In 'physical' terms, I'm not sure. One of the standard drives in maths is to generalize stuff, by saying 'lets take this thing that we're used to dealing with and see if there's anything that obeys most but not all of the same rules as it.' This starts with generalizing numbers and polynomials to abstract algebraic structures and generalizing intuitively 'real world' geometry to metric and topological spaces, but we're now getting to the stage where, for instance, the set theory and even the logical systems that in some sense underpin the whole lot are getting generalised on, or the notion of a bunch of structures or a spaces being abstracted to give category (nothing to do with the philosophical sense afaik) theory.
Once you've come up with some different axioms for a set theory or whatever, the obvious thing to do is to see what the sort of maths that you can do with it looks like, so I'd assume that a fair bit of that goes on. Versions that include the axiom of choice have always been known to provide 'useful' results which is why the axiom was postulated, but I think that versions that include its negation have also turned up interesting stuff. And I've been to a few category theory seminars that have involved laboriously constructing basic mathematical structures using a massively ass-backwards framework, to see if they behave normally. But I don't know if anyone's actually speculated about a universe where the laws
have to be framed in these terms. The closest I can think of at the moment is people using set theories that don't use the axiom of foundation (which normally forbids sets from being members of themselves or members of members of themselves or whatever) so they can naturally model self referential data structures in theoretical computer science.
Oh hang on, and I think a few people have started using "quantum logic", where the AND operator is replaced by AND THEN in the hopes of making the time dependancy of quantum into a feature of the mathematical language. But I'm not sure whether they're getting anywhere.
I really should take some math courses when I'm back in school, it's not fun to be totally clueless about these things.
Maybe go for set theory and mathematical logic and the foundations of computer science (Turing machines, the lambda calculus, that sort of stuff) over straight up maths? Maths is great, but it does take quite a commitment of time and effort before you get to anything really interesting, and the philosophical side you only really pick up from talking to other mathematicians. Maybe my perspective on what's 'really interesting' is skewed by being at the back end of eight years of study, though.
FWIW and IMO
this is a really good introduction to mathematical logic. It was originally written as a series of maths lectures aimed at philosophy students, so it's in the mathematical style but doesn't assume that you're already familiar with that way of working. In any case, I used it when I was doing undergrad set theory and it was handy, and has some really good stuff about incompleteness, the failure of set theoretic reductionism, models and so on.
Sorry, that was an epic pile of maths geekery.

And I might be offline for a few days so I probbaly won't be able to get back to people immediately...