ABSTRACT: What is a pattern? How do we come to recognize patterns that we've never seen before? Formalizing and quantifying the notion of pattern and the process of pattern discovery go right to the heart of scientific practice. Over the last several decades science's view of nature's lack of structure—its unpredictability—underwent a major renovation with the discovery of deterministic chaos. Behind the veil of apparent randomness, many processes are highly ordered, following simple rules. As the new millennium begins, tools adapted from the theory of computation will bring empirical science to the brink of automatically discovering patterns and quantifying their structural complexity. For example, rather than interpreting a data stream according to a given model, we look at a model stream. The regularities found in the way models improve with learning is the basis for inferring universal laws on how complexity arises from the interaction of order and chaos.
[A popular essay solicited to appear in The Sciences, New York Academy of Sciences, New York (1994). Sadly, NYAS no longer publishes The Sciences. February 2002: This version is somewhat updated from the original, written in 1992: citations have been added and dated comments edited to read less obviously a decade old.]