| After Turning and Church put forward the compute theory, the concept of compute has permeated into many fields of the science. The recent developments in cosmography,physics, biology, life sciences, artificial intelligence, artificial life , even the social science and economics etc. all express a common idea -"computation" and "algorithm" is very important in understanding our world and life. Because of the facts that the concept of "computation" and "algorithm" has permeated into many fields as listed in the preceding context and got so many achievements, a group of scientists sang high praise for the importance of "computation" and "algorithm". They hold the idea as such: The whole world is controlled by an algorithm and it is running according to the rule of it. The universe is a huge computing machine. Everything in the nature is a computing procedure. The variety of the world is a reflection of the different inner algorithm complexity. The essence of life is computing. The features of life such as thinking, birth, growth, heredity, self-production are all computing. This idea is called "computationism" or "algorithmism". The research of CA theory is a hotbed of computationism. Thus, to understand CA is a good way to understand computationism. In the 50s of last century, von Neumann brought forward the concept of CA with the inspiration of Ulam. CA is a dynamical system. It is defined on a cellular space, which consists of cells that has discrete, infinite states, and it runs in the discrete time dimension according to the local rules. Conway found the "Game of Life" in 1970. It is a 2-d CA. We can get infinite interesting patterns by limited initial configuration. Conway proved it has computational equivalence as the Universal Turning Machine. In 1984, Wolfram gave a dynamics classification for CA based on his research on ECA. Class 1: rapidly forget the initial state and is absorbed to a fixed state. It can be compared with the point abstractor in the continuous dynamics. Class 2: there many different possible final states, but all of them consist just of a certain set of simple structures that either remain the same forever or repeat every few steps. It can be compared with the periodic abstractor in the continuous dynamics. Class 3: always in a chaos, unordered states and seen in many respects random. It can be compared with the strange abstractor (or chaotic abstractor)in the continuous dynamics. Class 4: some local structures remain fixed, but some others move around and they interact with each other in very complicated ways. These complicated structures is neither absorbed into fixed or periodic states, nor becoming overactive because of randomness. It has no correspondent pattern in continuous dynamics. Wolfram pointed out that "Game of Life" belongs to class 4. Further more, Langton found the relation of the four classes by finding a parameter λ. With λ increasing from 0 to 1, CA will change its behavior from class 1 to class 2, then to class 4 and finally to class 3. Langton put forward the concept of "the edge of chaos" according to the feature of class 4 behavior. He pointed out that the CA of class 4 is running at the edge of chaos. At the same time, he announced that many systems have a state similar to "the edge of chaos". When in such a state, the system behaves complicatedly: the components of the system never fix, and never collapse. The system can save information steadily, and also disseminate information rapidly. This kind of system is robust and adaptive. It has the features of life. It can calculate in a complicated way and then respond to the outer world.Langton also found that phase transformation and the computer which is undecidable are all running at the edge of chaos. He then advanced a hypothesis that life comes from the edge of chaos. Later, he initialed a new science called "artificial life". Later more and more facts in various fields proved that the concept of edge of chaos has common sense. When CA theory came into application extensive...
|
PDF Full Text Request