There are several kinds of "theory". The CTMU is certainly a theory in the general sense that it is a descriptive or explanatory function T which takes the universe U as an argument: T = T(U). However, instead of employing logical deduction to derive theorems from axioms, it employs logical induction to derive the overall structure of reality from certain necessary properties thereof (which are themselves deduced from the facts of existence and perception). That is, it derives the unique structure capable of manifesting all of the required properties.
Logical induction does not have to assume the uniformity of nature; it can be taken for granted that nature is uniformly logical. For if nature were anywhere illogical, then it would be inconsistent, and could not be coherently perceived or conceived. But if something cannot be coherently perceived or conceived, then it cannot be recognized as reality, and has no place in a theory of reality. So for theoretical purposes, reality exhibits logical homogeneity, and logical induction thus escapes Hume's problem of empirical induction. (Q.E.D.)
The CTMU elevates empirical induction to the model-theoretic level of reasoning, thus circumventing the problem of induction.