So, I don't think protein folding adds much complexity to the result; it's more like a general purpose programming language than a set of specific library funct

So, I don't think protein folding adds much complexity to the result; it's more like a general purpose programming language than a set of specific library functions. This is dead on. The reason that library functions enable great code compression at higher levels is that they are designed specifically to enable code compression for the expected high level uses. Library designers pick out a small subset of all possible programs, and write their library code so that those programs can be expressed efficiently. Unless protein folding has, by sheer chance, ended up working just right to make wiring up an intelligent brain especially easy (and I'm not talking about the physical wiring, but the logical wiring), then it's silly to expect that it adds much information. On the other hand, the complexity of protein folding is vitally important for efficient evolution of any structure, and this is something that we need to take to heart: even if the complexity doesn't add much information, it allows small differences in the genotype to create massive differences in the phenotype. This shuffles regions of the fitness landscape around, so that in certain areas evolution is not so much climbing a hill as it is bouncing around atop a frothy unpredictable fractal. It's a fantastically clever way to avoid getting stuck in local maxima while still retaining a lot of the advantages of local search, as long as your fitness landscape has enough high points on it and the shuffling is not too severe.