Oh, and I suppose evolution is trivial? [...] By comparison... yeah, actually.
Nature was compressing the search space long before large brains came along.
For example, bilateral symmetry is based partly on the observation that an even number of legs works best. Nature doesn't need to search the space of centipedes with an odd number of legs. It has thus compressed the search space by a factor of two. There are very many such economies - explored by those that study the evolution of evolvability.
Surely this is not an example of search-space compression, but an example of local islands of fitness within the space? Evolution does not 'make observations', or proceed on the basis of abstractions.
An even number of legs 'works best' precisely for the creatures who have evolved in the curtailed (as opposed to compressed) practical search space of a local maxima. This is not a proof that an even number of legs works best, period.
Once bilateral symmetry has evolved, the journey from bilateralism to any other viable body plan is simply too difficult to trav...
Followup to: Life's Story Continues
Imagine two agents who've never seen an intelligence - including, somehow, themselves - but who've seen the rest of the universe up until now, arguing about what these newfangled "humans" with their "language" might be able to do...