Blog Dump 2: The Universality of Search

Searching is a much-studied area of computer science. The reason for this is that, like the Travelling Salesman Problem, the problem of how to search can be applied to a massive number of problems if they are phrased in the right way. As a straightforward example (if you’ll excuse the pun) let’s look at navigation: How do I get from Sheffield Train Station to the Devonshire Cat pub? This can be modelled quite literally as a search problem if you take all of the roads heading away from the train station (this is called enumerating them) and for each one, see if it ends up at the Devonshire Cat. If none do then enumerate all of the roads you found coming off them and do the same thing. Keep going until you either find the Devonshire Cat, or you run out of roads.

Another example this can be applied to is deciding where to eat with a group of friends. Here you can either enumerate the venues and search through them for the best match with your group’s preferences, or enumerate the preferences and search through those until the best venue is found.

The shear generality of search is what makes it fascinating. Indeed, for any problem where you know the answer is in a certain set of possible answers, and you have some way to verify the answer (equivalent to rating each venue in the dining out example) then you can enumerate the possible answers and check each one. The problems with this approach are pretty obvious: firstly the set of possibilities could be unfathomably large (eg. trying to find the first sentence of this post, if we were to first enumerate 1-character-long sentences, then 2-character-long sentences and so on then we would only find it after looking through about 2,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possibilities, which according to this site is pronounced “two quattuorvigintillion”), then of course there are infinite sets like the natural numbers, where we can start counting through them but we’ve no idea how long it may take to find the answer we’re after, and then there are non-recursively-enumerable sets, which means that not only can you not know how long it will take to look through, but you can never even find a way to go through every member of the set (for example, trying to enumerate the Real numbers, eg. with a decimal point, then there will always be an infinity of numbers between those we decide to test which will be skipped, no matter how we choose them).

Once again, it trails off before making any real point :P