I haven't thought about any of this for ages, but doing a bit of reading, it appears that decision trees *are* (or can be) universal approximators, but *only* on their training set. Unlike many neural nets, they don't generalize very well (or at all) beyond their training set.
Yet generalization is almost always what we need. We want to train these things on set A and then test them on set B. If the test is also on set A, it's sort of cheating; it can just memorize set A.
That makes them one-to-one with simple lookup tables, albeit ideally compressed versions, which obviously suffer an exponential explosion with the size of the input.
There apparently is also an application of the No Free Lunch "theorem" here, although I'm still somewhat vague on it.
However, the NFLT to me is obviously the same as the non-existence of universal compressors. For any algorithm that reversibly compresses set A, there exists a set B that that algorithm will make larger instead of smaller.
That's a theorem somewhere; not sure what its formal name is.
