I'm not sure what kings of pattern matching you have in mind. Possibly you mean the sort of "pattern matching" typical to narrow AI e.g. a neural network firing with response to a certain "pattern". Usually it is just clustering by dividing spaces with hypersurfaces constructed from some (very restricted) set of mathematical primitives. This sort of "pattern matching" is probably very important to the low-level working of the brain and the operation of unconscious systems such as visual processing, however it is not what I mean by "pattern matching" in the current context. I am referring to patterns expressible by language or logic. For example, if you see all numbers in a sequence are prime, it is a pattern. If you see all shapes in a collection are convex, it is a pattern. This sort of patterns are of fundamental importance in conscious thought and IMO can only be modeled mathematical by constructions akin to Solomonoff induction and Kolmogorov complexity.

There is a large multiplicative factor but it's not what you're describing.

On each step, AIXIt loops over all programs of given length and selects the one with the best performance in the current scenario. This is exponential in the length of the programs.