Trial and Errer

The No Free Lunch Theorem says that there's no one best search algorithm that works over all inputs. This makes perfect sense from Complexity Theory viewpoint. Suppose you're looking for a point x with some property (maybe we're maximizing a function over a domain). Because we're dealing with all possible landscapes, on average there's no information shared between points about who's the biggest. This is unlike, say, a monotone increase set of values where all we have to do is keep climbing in the right direction. In general, the identification of each point can't be any simpler than the information contained in its name. So over the set of all 10-bit numbers, it takes 10 bits on average to describe them. If we could find a general way of identifying each of them in less than 10 bits, we've found a miraculous data compressor indeed--one that can cram 10 full bits into 9!

This reminds me of a crackpot scientist's letter I got some years ago. He claimed to have designed a data compression scheme that would allow everyone in the world have a one-digit phone number! He even had a drawing of the phone.

Well, given that there's no free lunch, how do we explain the success of science in figuring things out? If I want to know how to fire a projectile so that it hits a target, I can figure out exactly what angle and velocity it should have without any trial and error whatsoever. The key to understanding that is that this is a well-explored domain, and Newton's laws of motion have demonstrated their efficacy at this kind of thing. Basically, this rests on symmetries--phenomena that seem the same time after time. It takes trial and error to find the symmetries, but once we've got them they save a lot of time. Undoubtably our brains are wired to look for such patterns.

This puts a fine point on the difference between the investigation of nature (purely trial and error) and the application of known theory (elegant solutions). So science and knowledge in general are messy on the outside and neat on the inside.

It makes me wonder if it's reasonable to expect a theory to straighten out all of the behavior we see around us. Isn't this asking too much? In other words, if the No Free Lunch Theorem says that averaged over all inputs nothing is better than random search, why would we expect to find a universal symmetry that allows elegant solutions to all problems? Maybe I've lost my way in the thicket between mathematics and physics, but it seems a fair question to ask.

Following the Complexity Theory line of thought, if it's true that the behavior of the universe boils down to a beautifully symmetric set of equations plus some initial conditions, then it must be the case that this accounts for all the information present in the universe for all time. That seems like a lot to ask of a theory.