Wednesday, October 31, 2007

Quantity Implies Quality

Quantity implies quality.

Example: In recent news, a professor searched 2,985,984 possible candidates for a universal Turing machine. In an earlier era when computing power was scarce, that may have been too many to search in a practical amount of time. But this guy found the answer. (Well, maybe.)

Example: Chess-playing is currently a prediction problem, but if resources increase enough to search the entire set of possible moves (which is theoretically possible as far as I understand the rules), winning becomes a search problem — which can always be solved. Think of tic-tac-toe. Or even checkers. In some games, a player with an abundance of computational power can look ahead to see which moves will lead to a win. Or at least a tie.

...I know what you're thinking. Wait, chess-playing is still a prediction problem. As with checkers, perfect look-ahead will tell you which moves will lead to the highest number of winning game-states compared to the total number of states. But your opponent, if he's smart enough, could always choose one of the ones that isn't a win for you. So it is more about predicting which moves your opponent will take. But I think this takes chess back to its roots — the fundamentals of a game.

The point is... some problems which are fundamentally search problems get transformed into prediction problems because the search-space is too large to be searched with current resources in a practical amount of time. Thus, the potential of a final right answer is lost.

By increasing resources to an abundance and using the law of Universal Substitution, you can re-convert problems back to search problems.

Quantity really does make a difference.

No comments: