Search Results

The authors of this chapter refer to the 1940s concept called cellular automata, which follows a naïve rule; cells in a rectangular grid undergo self-organized dynamic growth without a central directing instance. The chapter briefly discusses the digital image processing techniques and computer graphics before moving its focus to cellular automaton. It explores the importance of cellular automata in the field of imagery together with a wide variety of other concepts, and emphasizes cybernetics, parallel computers, vision chips, virtual reality, and a universal synthesizer and score. The authors state that cellular automata are mathematical pictorial models, which do not have any predecessors and are open to new artistic concepts.

When a dynamical system has significant spatial extent, its nonlinear dynamics can lead to the spontaneous formation of spatial patterns. Such systems provide models for how nature might have developed ordered, spatial structures from disordered states. Examples are given from fluid flow, transport models, coupled-oscillator modes, cellular automata, transport models, and reaction-diffusion systems. Diffusion-limited aggregation, viscous fingering, and dielectric breakdown provide further examples of pattern formation. Fractal structures make another appearance in this new context. This chapter also explores the somewhat controversial topic of self-organized criticality which has been put forward as an explanation for the occurrence of fractal structures in nature.

Chapter 2 reviews the development of the network-based agent-based models. From the behavioral and decision-making perspective of agents, the network-based agent-based model is accompanied by the neighborhood-based decision rules. The chapter divides the literature into two parts. The one developed before the advent of modern network science normally relies on the one-dimensional or two-dimensional lattices (cellular automata). The one developed with the advent of modern network science relies on the newly proposed network generation algorithms. In a chronological order, the chapter demonstrates the two-generation network-based agent-based models via a number of pioneering works. The purpose of these demonstrations is to show how network topologies can affect the operation of various economic and social systems, including residential segregation, pro-social behavior, oligopolistic competition, market sentiment, sharing of public resources, market mechanism, marketing, and macroeconomic stability. Cellular automata as the theoretical underpinning of undecidability and unpredictability for the dynamics on networks are also introduced.

Two-dimensional, discrete dynamical systems consist of two continuous variables, x and y, that get updated at discrete time intervals via a deterministic function. These variables are continuous because they can assume any value other than integers. This chapter focuses on cellular automata, a type of dynamical system with a large number of discrete variables that are arranged in an array or grid and then updated at discrete time steps via a local, deterministic rule. It begins with a simple example in which the variables can take on only two different values, visualised as white or black boxes. It then considers a rule which, when applied to a random initial condition, gives rise to a space-time behaviour. It also looks at chaos, the behaviour of cellular automata using a single-cell seed, and naming conventions for cellular automata.

We illustrate growth phenomena in two-dimensional cellular automata (CA) by four case studies. The first CA, which we call Obstacle Course, describes the effect that obstacles have on such features of simple growth models as linear expansion and coherent asymptotic shape. Our next CA is random-walk-based Internal Diffusion Limited Aggregation, which spreads sublinearly, but with a shape which can be explicitly computed due to hydrodynamic effects. Then we propose a simple scheme for characterizing CA according to their growth properties, as indicated by two Larger than Life examples. Finally, a very simple case of Spatial Prisoner’s Dilemma illustrates nucleation analysis of CA. In essence, analysis of growth models is an attempt to study properties of physical systems far from equilibrium (e.g., Meakin [34] and more than 1300 references cited in the latter). Cellular automata (CA) growth models, by virtue of their simplicity and amenability to computer experimentation [25], have become particularly popular in the last 20 years, especially in physics research literature [40, 42]. Needless to say, precise mathematical results are hard to come by, and many basic questions remain completely open at the rigorous level. The purpose of this chapter, then, is to outline some successes of the mathematical approach and to identify some fundamental difficulties. We will mainly address three themes which can be summarized by the terms: aggregation, nucleation, and constraint-expansion transition. These themes also provide opportunities to touch on the roles of randomness, monotonicity, and linearity in CA investigations. We choose to illustrate these issues by particular CA rules, with little attempt to formulate a general theory. Simplicity is often, and rightly, touted as an important selling point of cellular automata. We have, therefore, tried to choose the simplest models which, while being amenable to some mathematical analysis, raise a host of intriguing unanswered questions. The next few paragraphs outline subsequent sections of this chapter. Aggregation models typically study properties of growth from a small initial seed. Arguably, the simplest dynamics are obtained by adding sites on the boundary in a uniform fashion.

Suppose you were to walk through a door and come out on the other side the day before; that would be travel backwards in time, as these chapters explain. However, is it at all possible? Chapter 12 addresses the question within the laws of physics, explaining that some laws prohibit it, some allow it in special circumstances, and others quite generally. Simple examples are considered, including a world of ‘cellular automata’, to explain what our best theory of space and time, general relativity says. Chapter 13 addresses the paradoxical nature of time travel: if you travelled back a day when you stepped through the door you cannot then stop yourself from doing so, whatever you try! By considering what we mean by saying something can or cannot be done, and what it means to have free will, the chapter explains why there is no real paradox.

Fredkin’s Billiard Ball Model (BBM) is a continuous classical mechanical model of computation based on the elastic collisions of identical finite-diameter hard spheres. When the BBM is initialized appropriately, the sequence of states that appear at successive integer time steps is equivalent to a discrete digital dynamics. Here we discuss some models of computation that are based on the elastic collisions of identical finite-diameter soft spheres: spheres which are very compressible and hence take an appreciable amount of time to bounce off each other. Because of this extended impact period, these Soft Sphere Models (SSMs) correspond directly to simple lattice gas automata—unlike the fast-impact BBM. Successive time steps of an SSM lattice gas dynamics can be viewed as integer-time snapshots of a continuous physical dynamics with a finite-range soft-potential interaction. We present both two-dimensional and three-dimensional models of universal CAs of this type, and then discuss spatially efficient computation using momentum conserving versions of these models (i.e., without fixed mirrors). Finally, we discuss the interpretation of these models as relativistic and as semiclassical systems, and extensions of these models motivated by these interpretations. Cellular automata (CA) are spatial computations. They imitate the locality and uniformity of physical law in a stylized digital format. The finiteness of the information density and processing rate in a CA dynamics is also physically realistic. These connections with physics have been exploited to construct CA models of spatial processes in Nature and to explore artificial “toy” universes. The discrete and uniform spatial structure of CA computations also makes it possible to “crystallize” them into efficient hardware [17, 21]. Here we will focus on CAs as realistic spatial models of ordinary (nonquantum- coherent) computation. As Fredkin and Banks pointed out [2], we can demonstrate the computing capability of a CA dynamics by showing that certain patterns of bits act like logic gates, like signals, and like wires, and that we can put these pieces together into an initial state that, under the dynamics, exactly simulates the logic circuitry of an ordinary computer.

We explore a variety of two-dimensional continuous-valued cellular automata (CAs). We discuss how to derive CA schemes from differential equations and look at CAs based on several kinds of nonlinear wave equations. In addition we cast some of Hans Meinhardt’s activator-inhibitor reaction-diffusion rules into two dimensions. Some illustrative runs of CAPOW, a. CA simulator, are presented. A cellular automaton, or CA, is a computation made up of finite elements called cells. Each cell contains the same type of state. The cells are updated in parallel, using a rule which is homogeneous, and local. In slightly different words, a CA is a computation based upon a grid of cells, with each cell containing an object called a state. The states are updated in discrete steps, with all the cells being effectively updated at the same time. Each cell uses the same algorithm for its update rule. The update algorithm computes a cell’s new state by using information about the states of the cell’s nearby space-time neighbors, that is, using the state of the cell itself, using the states of the cell’s nearby neighbors, and using the recent prior states of the cell and its neighbors. The states do not necessarily need to be single numbers, they can also be data structures built up from numbers. A CA is said to be discrete valued if its states are built from integers, and a CA is continuous valued if its states are built from real numbers. As Norman Margolus and Tommaso Toffoli have pointed out, CAs are well suited for modeling nature [7]. The parallelism of the CA update process mirrors the uniform flow of time. The homogeneity of the CA update rule across all the cells corresponds to the universality of natural law. And the locality of CAs reflect the fact that nature seems to forbid action at a distance. The use of finite space-time elements for CAs are a necessary evil so that we can compute at all. But one might argue that the use of discrete states is an unnecessary evil.

This chapter contains an overview of experiments and theories on segregation occurring in heterogeneous granular materials. One of the most fascinating features of heterogeneous (i.e., consisting of different distinct components) granular materials is their tendency to segregate under external agitation rather than to mix, as one would expect from the naive entropy consideration. Various basic segregation mechanisms (e.g., entropic segregations, kinetic sieving, granular convection, condensation, etc.) and various experimental manifestations of granular segregation (e.g., granular stratification in surface flows, radial and axial segregation in rotating drums and related theoretical concepts, including discrete cellular automata and continuum phenomenological models) are discussed.

This chapter shows how complex shapes and forms encountered in the natural world result from a growth process driven by the repeated action of simple “rules.” To examine this general idea, the chapter focuses on cellular automata, arguably the simplest type of computer programs conceivable yet can sometimes exhibit behaviors that are extremely complex. Cellular automata are also a classic example of simple rules being able to produce complex global “patterns” that cannot be inferred or predicted even if we have complete, a priori knowledge of these rules. The chapter first considers cellular automata in one and two spatial dimensions before discussing a zoo of two-dimensional structures from simple rules. It then describes the role of agents in iterated growth as well as emergent structures and behaviors that can be produced by cellular automata. The chapter includes exercises and further computational explorations, along with suggested materials for further reading.

Suppose you were to walk through a door and come out on the other side the day before; that would be travel backwards in time, as these chapters explain. However, is it at all possible? Chapter 12 addresses the question within the laws of physics, explaining that some laws prohibit it, some allow it in special circumstances, and others quite generally. Simple examples are considered, including a world of ‘cellular automata’, to explain what our best theory of space and time, general relativity says. Chapter 13 addresses the paradoxical nature of time travel: if you travelled back a day when you stepped through the door you cannot then stop yourself from doing so, whatever you try! By considering what we mean by saying something can or cannot be done, and what it means to have free will, the chapter explains why there is no real paradox.

Building upon the preliminary materials introduced and the skills developed in previous chapters, we now focus on a few models developed for social-work-related research. Two models are presented. The first, involving travel training for persons with an intellectual disability, shows the results of learning to use public transportation and how that increases the persons' ability to move about their community. The second is a model of housing patterns for persons with intellectual and developmental disabilities, which demonstrates how the housing pattern becomes randomly distributed as people with disabilities moved from highly segregated institutional patterns to more inclusive community-based housing. Those planning on developing agent-based models are encouraged to review these materials and copy the code into the NetLogo procedures interface to gain an understanding of how the models operate.

According to pancomputationalism, everything is a computing system. Alleged sources of pancomputationalism are listed. This chapter distinguishes between different varieties of pancomputationalism and discusses arguments for the different varieties. Versions of ontic pancomputationalism, according to which the Universe is a computing system, are described in relation to platonism and Pythagoreanism, and are rejected. A more explicit and precise taxonomy of legitimate senses in which something may be described computationally is provided. This chapter finds that although some varieties are more plausible than others, only the most trivial and uninteresting varieties are true. As a side effect of this exercise, the chapter sharpens the distinction between computational modeling and computational explanation.

This chapter describes sound art and its influence under the digital simulations, which are based on artificial life models. It mainly focuses on the effects of the software concept on musical culture. The next part of the chapter outlines the definition of the algorithm and its role in software-based audio. The chapter also discusses the recent developments in the field of software music along and explores the relationship between cellular automata and music algorithms. Its main aim is to show the enormous efforts of artificial life techniques, the use of computers, and simulations in the art of music.

At first blush, computing and biology seem an odd couple, yet they formed a liaison of sorts from the very first years of the electronic digital computer. Following a seminal paper published in 1943 by neurophysiologist Warren McCulloch and mathematical logician Warren Pitts on a mathematical model of neuronal activity, John von Neumann of the Institute of Advanced Study, Princeton, presented at a symposium in 1948 a paper that compared the behaviors of computer circuits and neuronal circuits in the brain. The resulting publication was the fountainhead of what came to be called cellular automata in the 1960s. Von Neumann’s insight was the parallel between the abstraction of biological neurons (nerve cells) as natural binary (on–off) switches and the abstraction of physical computer circuit elements (at the time, relays and vacuum tubes) as artificial binary switches. His ambition was to unify the two and construct a formal universal theory. One remarkable aspect of von Neumann’s program was inspired by the biology: His universal automata must be able to self-reproduce. So his neuron-like automata must be both computational and constructive. In 1955, invited by Yale University to deliver the Silliman Lectures for 1956, von Neumann chose as his topic the relationship between the computer and the brain. He died before being able to deliver the lectures, but the unfinished manuscript was published by Yale University Press under the title The Computer and the Brain (1958). Von Neumann’s definitive writings on self-reproducing cellular automata, edited by his one-time collaborator Arthur Burks of the University of Michigan, was eventually published in 1966 as the book Theory of Self-Reproducing Automata. A possible structure of a von Neumann–style cellular automaton is depicted in Figure 7.1. It comprises a (finite or infinite) configuration of cells in which a cell can be in one of a finite set of states. The state of a cell at any time t is determined by its own state and those of its immediate neighbors in the preceding point of time t – 1, according to a state transition rule.

This chapter discusses the ancestor of the Lattice Boltzmann, the Boolean formulation of hydrodynamics known as lattice Gas Cellular Automata. In 1986, Uriel Frisch, Brosl Hasslacher and Yves Pomeau sent big waves across the fluid dynamics community: a simple cellular automaton obeying nothing but conservation laws at a microscopic level was able to reproduce the complexity of real fluid flows. This discovery spurred great excitement in the fluid dynamics community. The prospects were tantalizing: around free, intrinsically parallel computational paradigm for fluid flows. However, a few serious problems were quickly recognized and addressed with great intensity in the following years.

The fundamental premise of the book is that cities and regions are complex, self-organizing, adaptive systems, and that they are therefore best understood by focussing on the processes by which they grow and structure themselves. The approach is thus algorithmic, using cellular automata (CA) based models, and emphasizes spatial structure as it appears in land use, population distribution, and economic activity, since cities function by virtue of that structure. Studies of urban form by architects and urban historians have tended to emphasize street patterns, and emerging from these studies is an opposition between planned and “organic” forms. Organic forms are the signature of self-organized systems, and they emerge naturally from the models described in this book. The models integrate the city with its region, and socio-economic with natural phenomena. They also raise fundamental issues in the methodology and philosophy of science.

The study of interactions between the computing environment and cultural societies is called ethnocomputing. This chapter investigates the sociocultural influences on computer science and also discusses the major technical elements in the field of ethnocomputational practice, with illustrations. Furthermore, the chapter explores the research directions and trends of Information and Communication Technology. The authors also focus on ethnomathematics, cellular automata, the famous Simputer project, a culturally embedded computing group, Native American Language Acquisition Toys, and several other project examples.