Alan Bachers
Neurofeedback Foundation

The field of neurofeedback captures in a practical way both the philosophy and application of NKS methods. When the human central nervous system is placed in a loop with itself using scalp electrodes and video displays, various attractor patterns of aberrant function (pathology) emerge as computationally reducible events.  These events can be displayed in graphic form using Joint Time-Frequency Analysis. In neurofeedback training, optima of reduced pathologic variability are rewarded.  With sufficient training, non-linear dynamical central nervous system states are entered, which I term class four space, defined as lowered negative variability and heightened flexibility and resilience. Following training, the previously defined attractor patterns 1) die off, 2) form new patterns of lessened intensity, or 3) emerge as newly nested patterns. With repeated training, the class four states are entered with greater ease accompanied by dissolution and eventual elimination of pathologic attractors. Subjective reports are of quantitative and qualitative improvements in human capacities, increases in peak performance, and decreases in physio- and psychopathology.

John M. Bacus
Rice University School of Architecture

The history of the creative act in the twentieth century can be framed as a continuous and deliberate abstraction of the artist from the work of art—with an increasing emphasis on the processes of creation over the products. Two particular examples of note in this abstraction are the recognition of autonomous art (as defined by Adorno and the Frankfurt School) and the rise of automatic works like those performed by John Cage. I believe that a centralizing idea for both these threads may be found in the notion of the automaton—an entity both autonomous and automatic which, in a Deleuzian sense, becomes simultaneously the creator and the creation of a work of art.

Connections to NKS in this framing of the arts are quite clear. The notion of an automaton itself is of course central to NKS, but more importantly, the practices of NKS research (performing searches of problem spaces, reliance on visualization, etc.) closely parallels the processes of post-modern artistic creation. In the twentieth century, there were many attempts to marry art and science. I believe that NKS allows for this marriage to work in far deeper and more collaborative ways that it ever has in the past.

Architecture is typically about solids and surfaces, but these present not inconsiderable computational problems. A brief foray into the complexities of computational origami (which might be used to compute constructible and inhabitable form from flat materials) convinced me of the non-trivial problems ahead. To follow NKS into this problem space, I needed to simplify things as much as possible. So I started my research by looking only at lines.

There is a precedent for this in drawing. First year drawing students often begin with simple line drawing—forgetting at the beginning about form, weight, light, etc. in an effort to focus strictly on the most elemental practices of drawing. My initial thought was that I should see if I could use NKS to draw lines as simply as a child.

One particularly useful analog here is found in blind contour drawing, where the draftsman must make a drawing using only one continuous line. As an added obstacle, the draftsman is prohibited from looking at the drawing until his pen is lifted. A computational analog for this kind of drawing is the L-system, where a string of instructions are fed sequentially to a drawing entity which travels across the paper one unit at a time until the instruction set has been exhausted, leaving a single continuous line as a historical record of the path it has followed.

To visualize cellular automata with an L-system, I mapped drawing instructions to digits in the CA. For example, in an elementary two-color CA, a 0 bit was mapped to an LF instruction, and a 1 bit was mapped to a RF instruction. There are several different ways in which this could be done, but even this simple mapping gave quite interesting results.

Manuel Baez
Carleton University

Nature’s fundamental processes inherently generate regulatory systems and patterns that correlate with the rich realm of natural phenomena. These fertile processes inherently involve elemental relationships that dynamically evolve into integrative systems with startling form and structure generating capabilities. Modern computer visualization and analyzing techniques are providing us with deeper insights into the ways the “operations of energy” interweave into dynamic cellular systems and structures that often recall the patterns and motifs found in nature, art, architecture, mathematics, biology, physics and music. When the generative potential and interrelated cellular patterns of these systems are analyzed, they can yield more comprehensive insights into emergent complex morphology. The intrinsic nature of these process-patterns reveals highly coordinated cellular relationships that are simultaneously stable and highly dynamic. Through systematic analysis of the dynamic potential of basic geometric relationships, a series of cellular units and hands-on experiential procedures have been developed that inherently allow for the intuitive discovery of the interrelationships between form, structure, and generative process. The form generating potential of these cellular units is explored by joining (or weaving) them together into membranes. The flexibility of the joints and their three-dimensional relationships, both within an individual cell and throughout the cellular membrane, generates a wealth of forms and structures through the emergent transformative and organizing properties of the integrated assembly. How the membrane is explored and segmented, will determine the forms and structures that can be discovered and developed. The work exhibited and presented in this conference is produced through this process. They are evolving works that explore the dynamics and generative properties of cellular units and their assemblies. The work seeks to explore how complex structures and forms are generated from initially random processes that evolve into morphologically rich integrated relationships. The morphological diversity revealed by this working and teaching method offers new insights into the complexity lurking within nature’s processes as revealed through modern scientific theories of Chaos, Complexity Fractal Geometry and Cellular Automata. The implications of these developments are relevant to the study of morphology, architecture and other diverse disciplines at a time when the ideas emerging out of our deeper understanding of complex phenomena are being embraced for conceptual inspiration.

James Bailey

The technology of the printing press, the nomenclature of the equation, and the subject matter of the physicist have formed the iron triangle of western science since the Renaissance. Numbers and equations are easy to print (which puts circles and lines on the defensive). Dead objects, the focus of physics, can be analyzed piece-meal and sequentially and hence go nicely into the nomenclature of numbers and equations and from there straight into books.

Now a new world may be aborning. Molecular biology has pretty much abandoned the book. It gets done on computer screens and over the internet. Highly parallel emergent phenomena such as evolution and adaptation are unlikely to ever find expression in numbers and equations. They are hungry for an alternative. And biology has now replaced physics as the master science.

This talk will argue that these are all of a piece. There will be no new iron triangle of books, physics, and NKS any more than there could have been a new iron triangle of sacraments, prayer, and physics in the Renaissance. Unless it all changes, it will all fall back to the old ways.

When NKS ideas communicate poorly in text, and they often do, perhaps we need to admit it and move straight to publishing programs. If legacy sciences like astronomy and physics are resistant to bold new ideas like NKS, and they are, perhaps we need to look more aggressively to the under-served worlds of the life sciences and social sciences where NKS is so inherently promising and where the need is so great.

This talk will seek to characterize this new world outside the book, drawing on current examples from biology, computer science, and a bit of blob-style architecture. It will also look at some past scientists, from Leonardo to Bergson to Whitehead, who tried unsuccessfully to communicate parallel emergent ideas in text form. If only they could have published programs.

Mel L. Barclay
University of Michigan School of Medicine

The process of birth in humans is powered by the action of the uterus. The forces it generates propel the infant as it passes from the intrauterine to the external environment. The uterus has patterns of behavior which are dependent on the basic physiology of muscular contraction. Muscle fibers are stimulated, respond to stimulation with mechanical activity, enter a refractory or unresponsive period, and then contract again. >From a modeling point of view, the uterus is structurally and functionally simple. There is a single pumping chamber and the uterine contents are propelled along a single outflow path.

The uterus in labor has many properties which suggest it may be capable of generating complex dynamical patterns of activity. It has elasticity, elements of slip and stick, play and backlash, and possibly nonlinear electrical conduction with feedback.

We have designed a cellular automaton to model uterine function. A Turing-type matrix of cells is applied to a single-layered surface, which has the shape of human uteri, derived from historical anatomic descriptions as well as mathematically generated ellipsoids and paraboloids of revolution. Individual cells are capable of stimulation, impulse transmission, contraction, a resting or refractory period, and then reactivation. Rules for impulse transmission to neighboring cells are specific as are the activation, contraction, and refractory periods.

Cells contract isovolumetrically generating one unit of pressure measured summatively at the center of the uterus according to Pascal's Law. This produces pressure waveforms similar to those observed in the uteri of laboring human females. Complicated emergent behaviors and patterns of depolarization including vortices have been observed which may provide additional insights into those factors that promote the initiation of premature and spontaneous labor.

Fig. 1 A phase-space diagram depicting the relationship between two cell states.  Two quite different areas are obvious. The upper region characterizes non-synchronous random or chaotic contractile activity that is not productive of organized uterine activity.  The lower region characterizes variable yet regular contractile activity, an emergent phenomenon.  A single pathway apparently connects the two domains.

Christopher C. Barton
U.S. Geological Survey

Sarah F. Tebbens
College of Marine Science, University of South Florida

Stephen M. Burroughs
Department of Chemistry and Physics, University of Tampa

The dynamics of the shoreline position at Duck, North Carolina generate a self-affine signal, a characteristic of scale invariant nonlinear systems. Persistence, a property of self-affine signals, is used to characterize internal correlations between historic mean-high-water (MHW) shoreline positions and to create forecast envelopes for probable future shoreline positions. We analyze 20-year time series derived from four transects surveyed by the U.S. Army Corps of Engineers at Duck, North Carolina. The spectral characteristics of the time series, including persistence and activity level, are determined using the Fast Lomb Periodogram. The four MHW shoreline position signals are self-affine with persistence, b, ranging between 0.8 and 0.9, indicating that each signal is stationary with weak internal correlation. This self-affine behavior indicates that changes in shoreline position arise from the collective random motion of sand grains. We use the self-affine properties of the historic record to forecast future shoreline behavior. This forecasting approach is in contrast to the traditional approach of extrapolating linear trend lines fit to historic shoreline positions, which assumes an underlying linear process with noise superimposed. Trend lines fit to the MHW shoreline signals vary depending on the subinterval considered, and therefore poorly characterize the signal and poorly predict future shoreline behavior. Using the parameters of the self-affine signal, we create forecast envelopes for probable future MHW positions. Forecast envelopes projected 50 years from the start of the record indicate that future shoreline positions will be within ±14 m of the mean MHW position of the 20-year record.

Christopher C. Barton 
U.S. Geological Survey

Jorge Gomez-Moreno
U.S. Geological Survey

We calculate the time it takes for precipitation to move through the catchment to the stream in the Watershed-6 at Hubbard Brook, New Hampshire. The catchment travel time is a fundamental hydrologic parameter that affects the retention of soluble contaminants in the watershed. Our tracer is Cl, which is conservative. Spectral analysis of the 35 year Cl concentration time series shows that the fluctuations over three orders of magnitude are fractal with a scaling exponent of 0.5 for precipitation and 0.7 for stream water measured at the weir. Therefore, the Cl fluctuations in the catchment are necessarily fractal, as are flow paths. A fractal distribution of catchment travel times means that after a contaminant pulse, concentration will initially drop rapidly, but then decline much more gradually and will persist for very long times.This “fat tailed” decay is characteristic of fractal distributions. Flow through the catchment dampens the chloride signal and increases the persistence of the signal, which permits calculation of the average flow time through the catchment. We fit the catchment spectrum with a power form of the Gamma distribution and calculate the average travel time through the catchment. The average flow time through the catchment is 3.7 months.

Stephen Wolfram
Wolfram Research

Kovas Boguta
Wolfram Research

Richard Phillips
Wolfram Research

Issues of both practical and intellectual interest shall be covered in this comprehensive session about The Wolfram Atlas of Simple Programs. The major components include an overview of the user interface design, a live demonstration by Stephen Wolfram on how the Atlas works as an example of NKS methodology, and a demonstration of the technology underlying the Atlas’s construction.

Bram Boroson

Stephen Wolfram’s work on fundamental physics in A New Kind of Science (NKS), particularly his trivalent network model, has features related to and yet distinguished from other models in the physics literature that have discrete elements, such as Loop Quantum Gravity (LQG). One important distinction between theories is whether quantum mechanics (QM) is “imported” without further explanation (as is currently done in LQG), or may arise as an emergent property (as in NKS). Most work on fundamental physics citing NKS seems not to be done through traditional refereed publications but through internet discussion groups (forum.wolframscience.com, digitalphysics on yahoo) or personal blogs. The multidisciplinary credentials of those influenced by NKS (often with more training in computer science than in physics) makes these discussants open to new ideas. In online groups, however, the participants often “talk past each other” and focus on their own pet ideas. This talk will attempt to remedy this situation by summarizing some NKS-influenced approaches and placing them on the continuum between imported/emergent QM.

Brenton Bostick 
Wittenberg University

The 3n+1 problem defines a function T(n) such that if n is even, then T(n) is n/2, and if n is odd then T(n) is 3n+1. The question is: after enough applications of T, do all integers eventually iterate to 1?

A cellular automaton (CA) was built that computes iterations of the function T. The CA given in NKS has a few drawbacks that warrant a new approach: it operates in base 6, an unfamiliar base for many people, and it constantly moves to the right, which is a distracting side effect. However, there are advantages: its rule table is stated simply in one update rule and works in only 7 colors. It also computes all digits of any one iteration in parallel.

My CA works in base 2. It has 9 colors. It has a fixed “binary point” color that acts as an anchor. It takes 2 time steps to compute a bit for each iteration, but multiple bits are computed in parallel.

Visualizing the evolution of the CA has aided me in thinking about the problem as an algorithm rather than a simple function. Several results concerning the interplay of the bits of the iterates have emerged. A potential new approach to solving the problem “algorithmically” is also discussed.

Mark W. Bultman,
U.S. Geological Survey 

F.S. Fisher
U.S. Geological Survey

Mark E. Gettings
U.S. Geological Survey

Coccidioidomycosis is a public health issue of increasing importance to people in the southwestern United States and in parts of Central and South America. It is caused by Coccidioides, a dimorphic soil-inhabiting fungus. The saprophytic phase of the fungus is characterized by branching segmented hyphae that form a network of mycelium in the upper horizons of soils.  As the fungus matures, it produces arthroconidia that can be separated by soil disturbance (natural or anthropogenic) and consequently dispersed by the wind.  If airborne arthroconidia are inhaled by an appropriate host, primary infection may occur and the parasitic phase of the Coccidioides life cycle is initiated.

Habitat modeling of the saprophytic phase of the Coccidioides life cycle is difficult due to the limited number of known growth sites. This confounds the determination of statistical relationships among physical, chemical, and biological habitat parameters. Laboratory and site-specific field studies have determined many of these parameters.  The modeling scheme therefore must use these parameters as input data and transform them into output that describes the favorableness of soil for hosting Coccidioides at all locations in the study area.The model should be able to deal with data of differing precision and accuracy and should reduce a potentially intractable number of model relationships to a smaller modeling framework with reduced dimension. The modeling technique chosen to do this is a fuzzy system. Because this modeling technique will be applied to a large number of spatially distributed cells within a raster Geographic Information System, the approach is referred to as a spatial fuzzy system.

In addition, a model of the spread and survival of Coccidioides in soil via wind-borne arthroconidia transport has been completed using public domain, agent-based modeling software.  The model results mimic what is seen in nature and indicates that complexity introduced in the model from site favorableness, temperature, moisture, and duration of favorable temperature and moisture conditions is adequate to explain observed distributions of real sites.

Paul Burdick 
New England Conservatory of Music 

MichaelGardiner
New England Conservatory of Music 

John Kiehl
New England Conservatory of Music 

Maurice Methot
Emerson College

Katarina Miljkovic 
New England Conservatory of Music

NKS 2003 brought together Paul Burdick, John Kiehl, and Maurice Methot to explore the relationship between NKS and music. A year later, they are here to report on their progress. Having established an NKS/Music workgroup at the New England Conservatory of Music in Boston, John, Paul, and Maurice are joined this year by Michael Gardiner and Katarina Miljkovic. Their workgroup’s focus has been twofold: (1) to understand and participate more fully in the intersection between NKS and music; and (2) to develop software that allows musicians and scientists to explore these connections on their own, by asking questions about NKS and making music. This session will feature the premiere of their new software CA-Cophony.

Paul Burdick 
New England Conservatory of Music 

Ed Pegg
Wolfram Research 

John Kiehl 
New England Conservatory of Music 

Michael Schreiber

Scientists ask one question and make a thousand things. Artists make one thing and ask a thousand questions. Are science and art just rhymes, or are they actually about the same thing? NKS presents an intriguing possibility and context for bridging these two paths in the practice, work, and lives of scientists and artists alike. This session will explore these ideas and suggest a framework for thinking about how artists and scientists might use NKS to forge real methods and procedures for working meaningfully together.

Jason Cawley
Wolfram Research

This will be a talk about the history of ideas about limits to knowledge, placing NKS ideas on the subject in historical context, from ancient Greek and Enlightenment periods to Pierce and Popper. Different arguments have been advanced as to the scope and origin of such limits. NKS irreducibility preserves intuitions from some of them and revises others.

Jason Cawley
Wolfram Research

Matthew Frank
University of Chicago

Do you have questions about the structure of the argument presented in the NKS book? About the meaning of its basic concepts or its implications for long standing questions in philosophy? What is the principle of computational equivalence, or computational reducibility? In what sense is the behavior of rule 30 random?  How does what NKS says about complexity in biological systems fit into evolutionary theory? Does the role of prediction change in NKS compared to previous science? What does NKS mean for—some other issue?  If you have questions like these, this session is a chance to get responses to them from members of the Wolfram Science Group and to discuss them with other conference participants.

NKS|Online: www.wolframscience.com/nksonline 
Oyvind Tafjord 
Wolfram Research 

Downloadable Programs 
Ed Pegg 
Wolfram Research 

CellularAutomaton 
Richard Phillips 
Wolfram Research 

Automata 
Klaus Sutner 
Carnegie Mellon University 

NKS Community Tools 
Ed Pegg 
Wolfram Research 

NKS Explorer/NKS Explorer: Mathematica Kit 
Oyvind Tafjord 
Wolfram Research 

NKS Forum: forum.wolframscience.com 
Jason Cawley 
Wolfram Research

Seth Chandler
University of Houston Law Center

This talk exposits in some detail the methodology developed in a fascinating recent paper by Israeli and Goldenfeld, and shows how Mathematica may be used to explore and extend their work. The purpose of this effort is to make their work more accessible and to permit a broader audience to conduct at least many of the relevant experiments.

Their paper attempts to shows that if certain micriscopic details are blurred together, for many elementary cellular automata, the long run behavior always emulates certain other cellular automaton.  Indeed, sometimes these approximating cellular automata exhibit behavior that is less complex than that of the original. And this is true even with respect to some (but apparently not all) Class 3 cellular automata that exhibit complex behavior. The paper thus suggests that, although some automata may be computationally irreducible, others hitherto placed in that category may have their behavior approximated (and thus reduced in some sense) using other cellular automata. The paper thus speculates as to whether Wolfram’s classifications of automata and the understanding of computational irreducibility he presented in A New Kind of Science may need some refinement.

This translational scholarship is important because cellular automata can help explicate the behavior not only of physical systems, but biological and social systems as well. And perhaps because Mathematica is such a natural language for the study of cellular automata, the code for accomplishing the translation proves relatively simple. To be sure, speed issues associated with Mathematica make it difficult as a practical matter to replicate the most complex experiments conducted by Israeli and Goldenfeld. This limitation might be softened to some extent by faster hardware, patience, or perhaps algorithms that exploit Mathematica more effectively than has been possible in this initial foray.  The analysis here suggests, however, that there may be more fundamental problems of computational explosion and irreducibility with trying to find approximating cellular automata that rely on larger block size.  Many cellular automata may retain their secrets.

Seth Chandler
University of Houston Law Center

A global cellular automaton (GCA) is a cellular automaton in which the evolution of each site is a function not only of the values of the site’s neighbors, but also of certain global features of the automaton. This notebook explores an extension of GCAs (abbreviated as a GCAN) in which each GCA is connected to other GCAs and each site of each GCA evolves not only according to the value of its local neighbors but also according to its own global features and those of its neighboring GCAs. GCANs may be useful in a variety of ways. First, they provide a vehicle for studying composition of cellular automata. Second, the concept of a GCAN, which is essentially one of complex agents interacting over a network, may be useful in emulating the computing systems or the interactions of complex agents.

Jesse Clark
Carnegie Mellon University

A key point of NKS is the computational universality of certain cellular automata. Sutner has constructed reversible one-dimensional cellular automata of intermediate (less than universal) Turing degree by simulation of  intermediate-degree Turing machines.

Sutner’s construction uses tracks that left-shift and right-shift their contents at every step, allowing for the propagation of signal bits  that simplify the Reachability problem. He has shown that the behavior of the signal system is trivial on finite configurations.

We examine the signal system and show that its behavior is trivial even on infinite periodic configurations. It is impossible to construct domain walls or produce behavior more complex than parenthesis-balancing, so it cannot increase the degree of an automaton beyond the degree of the Turing machine being simulated.

The signal system is not strictly reversible: there are “Garden of Eden” states which can have no ancestor. However, this does not introduce ambiguity to the simulation of a legitimate Turing machine. We analyze the consequences of semi-reversibility for the Confluence and Reachability problems.

Ricardo Colasanti 
National Research Council, USEPA NHEERL WED, University of Glamorgan 

Rod Hunt
University of Exeter

Lidia S. Watrud
USEPA NHEERL WED

The development of models is of interest to ecologists, regulators, and developers, since it may assist theoretical understanding and decision-making in experimental design, product development, and risk assessment. A successful modeling methodology for investigating such characteristics must include both a plant’s spatial and functional behavior within a plant community as a function of its physiology. However, can the full dynamics of a plant community emerge from the physiological properties of its constituent species?

Over the last twenty years successful simulations of spatial processes of vegetation have been conducted by a number of authors (Barkham & Hance 1982; Crawley & May 1987; Green 1989; Inghe 1989; Colasanti & Grime 1993) using a cellular automata (CA) method of modeling where a plant’s distribution within a two-dimensional environmental grid is determined by rules relating to phenomena such as seed dispersal, clonal expansion, and interactions with adjacent plants. We believe that these same methodologies can be utilized in order to predict the potential impacts of genetically modified (GM) plants. To do so we must understand how the engineered traits are expressed in an ecological context.

It would be a daunting task to experimentally evaluate the full multiplicity of potential pair-wise interactions between GM plants and native plants under a broad variety of actual environmental conditions. We propose, therefore, to model interactions between GM plants and the natural environment by describing the plants and the effect of the GM trait in terms of plant functional types (Grime 1979). This approach takes the external factors which limit the amount of plant material present in any habitat and classifies them into two categories: (1) stress, defined with regard to the availability of nutrients, and (2) disturbance, which refers to the destruction of plant material. The ecological characteristics of plants both natural and genetically modified can be described based on functional type, i.e. as determined by their quantifiable physiological relationships to stress and disturbance. By ascribing the large number of plant ecological characteristics to a smaller number of functional types the problem becomes tractable.

The presentation will describe a CA individual-based model constructed from a plant functional type rule base, that does indeed reproduce all of the main population attributes and vegetation processes that are observed in field conditions. Competition (both natural and genetically modified) in relation to environmental factors (both natural and man-made) has been successfully simulated in considerable detail. We will also describe how the model will be validated using data from field and mesocosm studies being carried out by researchers from WED.

References: Barkham JP, Hance CE. 1982. Population dynamics of the wild daffodil (Narcissus pseudonarcissus) III Implications of a computer model of 1000 years of population change. Journal of Ecology 70: 323-344. Colasanti RL, Grime JP. 1993. Resource dynamics and vegetation processes: a deterministic model using two-dimensional cellular automata. Functional Ecology 7: 169-176. Crawley MJ, May RM. 1987. Population dynamics and plant community structure: competition between annuals and perennials. Journal of Theoretical Biology 125: 475-489. Green DG. 1989. Simulated effects of fire, dispersal and spatial pattern on competition within forest mosaics. Vegetatio 82: 139-153. Inghe O. 1989. Genet and ramet survivorship under different mortality regimes - a cellular automata model. Journal of Theoretical Biology 138: 257-270.

Gautam Dasgupta
Columbia University

Céline Lannier
Columbia University

In engineering mechanics, computational tools are developed according to the underlying partial differential equations.  However, problems such as turbulence necessitate the NKS approach. Similar observations are made for situations where qualitative parameters drive the numerics.

This research team is exploring formulations using the appropriate NKS tools to systematize calculations related to architectural designs, bio-morphometry, security engineering with the LiveDesign paradigm, and socio-economic issues related to sustainable tourism development. For example, in a linear design environment the rules do not evolve hence Mathematica objects related to Nest are relevant. In social science the rules evolve and problems require analysis using Fold. Highly nonlinear evolutionary processes in biology can be similarly captured using FoldList to display the distinct steps of the phenomena that appear when examining Plio-Pleistocene fossils.

Additionally, a progress report on security engineering and anthropological studies with endocasts of skulls will be presented.

George Danner
Industrial Science, LLC

NKS promises to have a profound effect on all branches of science—in particular, highly complex phenomena we observe in nature. Yet we also know that complexity is not the exclusive domain of science—problems in business can have the same level of detail and dynamic complexity. More than a few researchers have already drawn parallels between science and business with the use of terms like “ecosystems” and “punctuated
equilibrium” to explain systemic behavior of businesses or industries.

In my remarks, I will be addressing the application of NKS to business. In a broad sense, I will discuss the conditions and history that have made NKS highly relevant to the study of business. Classes of problems in business will be mapped to particular strengths of NKS in generating appropriate insight. Moreover, I will present a problem archetype, the so-called Easter Egg Problem, as an example of applied research in the area.

Andreas Eckerstorfer 
Johannes Kepler University Linz

A rotation-invariant algorithm for a self-acting inspection system to detect scratches in grayscale images of ground metallic material will be discussed. Scratches are darker curves on the image, which can easily be detected with our eyes. So it is obvious to use the methods of visual perception presented by Stephen Wolfram.

The algorithm is divided into three main parts.

1. Halftoning

Each pixel-value is compared with the average pixel-value in a small neighborhood of 3x3 pixels. If the pixel is much darker than the neighborhood and the pixel itself is not too light, the new pixel is set to black, otherwise white. By this method the information about the scratches is preserved.

2. Searching of small line segments

As a variant to the approach presented, only the correspondence between the black cells of different line segments and the neighborhood of each pixel of the halftoned image is observed. If this correspondence is high, the new pixel at the center of this neighborhood is set to black.

3. Scratch classification

Now the resulting image is partitioned into stripes of the same direction as the line segment used in step 2. If the number of black pixels in one of these stripes is much larger than the number of black pixels in the other stripes, then with high probability there must be a scratch in this stripe. If no scratch is found, the material passes the inspection.

As an example this algorithm is applied to a typical image.
original image:						“scratch.bmp”
halftoned image:						“halftoned.bmp”
the correspondences with two special line segments:		“25degreeimage.bmp,” “85 degreeimage.bmp”

With stripes of 10 pixel width both scratches in the original image are detected.

Matthew Frank
University of Chicago

What must a computation be in order for the principle of computational equivalence to hold? Two years of struggle with and correspondence on this question have left me with no clear answer about computational equivalence, but several insights about the peculiarities of the NKS notions of computation versus notions more familiar in mathematics. I present some of these insights, along with a more successful outcome to a briefer struggle with the principle of computational irreducibility.

Dimitry Gashinsky
RSA Security

A universal machine can simulate any effective process of symbol-manipulation, be it mathematical or anything else. It is a completely general instruction-obeying mechanism. In current practice, any actual computer approximates an ideal universal machine.

Cellular automaton (CA) rule 110 is a universal machine, so in theory it is capable of emulating any other machine.

I will be talking about my long term project to write a compiler for initial conditions of CA rule 110 from a higher level language. I think that it will have practical uses in the nanotechnology or in field-programmable gate array technology.

The first step of this project is to create a symbolic representation scheme for structures in rule 110. It will allow for easier experimentation with different initial conditions. The second step is to read back the output of the evolution of CA rule 110 and automatically produce symbolic representation of the structures. These two steps will allow me to catalog all of the interesting collisions between structures in CA rule110 in a symbolic form.

It is required to study the interactions between hundreds of structures in order to emulate complex computation in evolution of rule 110. The techniques that I discuss will allow me to do that without complex custom graphical tools.

Evangelos Georgiadis
Wolfram Research

I investigated implications of simple deterministic rules in International Relations. The objective was to look at a 2 alliance, multi power system with a simple deterministic alliance switching rule and two alternate power updating rules. I, then, varied power number, initial power for each, and the initial alliance configuration. I found two basic forms of behavior, each rather simple but one less stable than the other.

Mark E. Gettings
U.S. Geological Survey

Phillip Hammonds
Northrop-Grumman Information Technology

Bernard P. Zeigler
Arizona Center for Integrative Modeling & Simulation

In one dimension, the multiplicative cascade can be viewed as a conservative system in which the contents are distributed into ever-decreasing size line segments by putting a portion of the contents of a line segment into each of the segments.  In the limit the set becomes one of an infinite number of members of infinitesimal size, each of infinite density. If the generation of the set is stopped at a finite number of steps (finite scale), the process models concentration of the contents on a line. The process can be generalized into unequal length segments and unequal (and nonzero) proportions allocated to each segment. This defines a general multiplicative process in which the final content of each segment is a product of the proportions from all the steps or generations of line division in the final distribution. If the order of applying the division and proportioning is randomized, distributions statistically identical to real distributions observed in earth science can be obtained. Two examples of application of the concentration model are the distribution of tonnage of ore as a function of deposit grade and the distribution of magnetic susceptibility in hydrothermally altered rocks in porphyry systems. In the latter model, the line division process determines the distribution of fractures. The susceptibility of interfracture blocks is modeled by oxidation of the wallrock, a process controlled by the diffusion equation. Multiple processes may be modeled by serial application of line division processes. The model can be further generalized to non-conservative systems if the sum of the proportions distributed to segments is not unity.  Sums greater than one represent systems accumulating mass from outside the system, while sums less than one represent systems losing mass. The concentration of selenium in the San Francisco Bay ecosystem can be modeled by such a series of superposed (non-conservative) line division models. The resulting distributions are complex and resist inversion to yield the concentration process parameters.

Nigel Goldenfeld
University of Illinois, Urbana-Champaign

Using elementary cellular automata (CA) as an example, I show how to coarse grain CA in all classes of Wolfram’s classification. The resulting coarse-grained CA emulate the large-scale behavior of the original systems without accounting for small-scale details. Computationally irreducible physical processes can be predictable and even computationally reducible at a coarse-grained level of description. At least one of the CA that can be coarse grained is irreducible and known to be a universal Turing machine.

Nigel Goldenfeld
University of Illinois, Urbana-Champaign

Can we use computational algorithms to make accurate predictions of physical phenomena? In this talk, intended for non-experts, I will explain that physical predictions, whether analytical or computational, are predicated on the following assumptions: (1) there exists a minimal model that is a caricature of the phenomenon in question; (2) there exists a renormalization group fixed point about which universal quantities can be calculated systematically; and (3) the desired predictions concern quantities that are universal at the appropriate fixed point.  I will give examples where this works and where it fails, and show that in some cases, complex space-time phenomena can be exquisitely captured with simple computational algorithms that not only produce patterns resembling those seen in experiments, but also make accurate predictions about probes of dynamics and spatial organization, such as correlation functions.

David Hillman

The idea of combinatorial dynamics is to define sets of n-dimensional combinatorial spaces in as general way as possible, and then to find elementary local invertible maps T:A->B between pairs of space sets so that all local invertible maps are generated by the elementary ones. Then if T:A->A is a local invertible map, its orbits {T^z x : z in Z} (for each space x in A) are (n+1)-dimensional combinatorial spacetimes. These systems include reversible cellular automata but are much more general: geometry can change over time; big bangs are possible. I’ll  introduce these ideas by looking in detail at the one-dimensional case.

Christian Jacob
University of Calgary

We are surrounded by a natural world of massively parallel, decentralized biological information processing systems, a world that exhibits fascinating emergent properties in many ways. In fact, our very own bodies are the result of emergent patterns, as the development of any multi-cellular organism is determined by localized interactions among an enormous number of cells, carefully orchestrated by enzymes, signalling proteins and other molecular agents. What is particularly striking about these highly distributed developmental processes is that a centralized control agency is completely missing. This is also the case for many other biological systems, such as termites which build their nests without an architect that draws a plan, or brain cells evolving into a complex “mind machine” without an explicit blueprint of a network layout.

Obviously, being able to understand, build, and harness the emergent properties of such systems would be highly beneficial. Designers of complex systems could utilize their adaptability and robustness. Such systems would construct themselves, through self-organization. However, system designers and programmers are facing an enormous challenge. How can we actually build highly distributed systems of which we have only limited understanding? Would we have to invent new ways of building, maintaining, and controlling such systems? It seems to be necessary to explore a completely new mindset for programming and system control. I intend to discuss computational biology models my Evolutionary & Swarm Design Group has investigated and built.  I will give examples of these models and discuss the specific aspects related to NKS. In particular, I will demonstrate how these systems can be designed through evolutionary techniques. The models to be presented are: 
• A swarm-based traffic simulation, with cars that communicate through “pheromones”.
• A rule-based and an agent-based 3D simulation of the Lactose Operon as a classical gene regulatory system.
• Agent-based 3D simulation of the Lambda Switch, a gene regulation system used by the bacterial phage.
• Agent-based 3D simulations of the human immune system.
• Genetic programming of dynamic swarm behaviors.

Bahman Kalantari
Rutgers University

Despite the very old history of the polynomial root-finding problem or the compuer visualizations that have emerged in the past few decades, its applications and mysteries are  far from being exhausted. This is contrary to the common belief, even among some experts in various fields. Polynomiography is the art and science of visualization in the approximation of zeros of complex polynomials via iteration functions. Polynomiography has numerous applications in art, science, and education. Like photography, iteration functions have the ability
to capture numerous “polynomiographs” of the underlying polynomial, images that may or may not exhibit fractal behavior. Like NKS, the iteration functions within polynomiography could be generated via simple programs, yet exhibit unpredictable and complex behavior. The Mathematica software and extensive NKS experiences strengthen the view that we should carry out polynomiography on larger and larger degree polynomials. This visualization not only could bring deeper insight into the nature of various classes of polynomials, but perhaps analogous to the problem of computing the digits of pi, it could bring about new scientific and mathematical challenges. However, unlike the problem of approximating digits of pi, polynomiography of large degree polynomials should bring to life new artwork, never seen before, perhaps worthy of appreciation by the millions.

Michael Kelly 
Illinois Institute of Technology

The traditional use of cellular automata in the study of scientific topics has been to specify simple rules and see whether the resulting CA structures behave like some known real world structure that the scientist wishes to model. To this end Stephen Wolfram specified a simple model for financial market price fluctuations in Chapter 8 of A New Kind of Science. While exhibiting the characteristic fractal property of market prices, this model did not allow an analysis of actual financial instruments. The evaluation of such instruments, especially financial derivatives, constitutes the main task of financial quants employed by banks and financial institutions. What this paper aims to do is show that the appropriate modification of the CA transformation rules makes it possible to implement efficient code for the evaluation of financial options by modelling the trinomial lattice structures that correspond to the partial differential equations that describe all option behavior.

The following graph shows the typical behavior of a European call option generated from a continuous cellular automaton utilizing a symmetric trinomial recursion rule.

Plot3D[CAEuropeanCall[S, 10, σ, 0.1, 0.03, 1],{S,5,15},{σ,0.15,0.3}]

⁃SurfaceGraphics⁃

Chad Kennedy
Arizona State University

For tissue engineering and cell therapeutics to become a reality, the diffusion limitation of nutrients to implanted cells and tissues needs to be overcome. In addition, the complexity of certain structures, such as the liver, have rendered traditional approaches very limited. Therefore, the purpose of this project is to generate classes of three-dimensional branching structures using rule-based L-systems, create a method of morphological analysis, and compare the morphological indices to that of physiological branching structures. These structures would serve as templates to build living complex constructs using rapid tissue prototyping technologies developed in parallel. In addition, patterns can be fabricated via traditional rapid prototyping techniques at a much larger scale as instructional tools for microanatomy and physiology.

Veikko Keränen
Rovaniemi Polytechnic

The systematic study of structures in words was started by Axel Thue in 1906. In 1961, Paul Erdös raised the question whether abelian squares can be avoided in infinitely long words. An abelian square means a non-empty word uv, where u and v are permutations of each other. For example, abc acb is an abelian square. A word is called abelian square-free if it does not contain any abelian square as a factor. For example, the word abacaba is abelian square-free, while ab cabdc bcacd ac is not. In 1992, we presented an abelian square-free (a-2-free) endomorphism g85 over the four letter alphabet. The size of g85 is equal to 4×85, and it was found after long computer experiments. Until very recently, all known methods for constructing arbitrarily long a-2-free words have been based on the structure of g85. In 2002, after over 11 years of exhaustive searches, we found a completely new endomorphism g98, the iteration of which produces an infinite abelian square-free word.

In our talk we explain the computer searches carried out for finding new ways of constructing a-2-free words. In this process we have encountered some unintuitive non-linear phenomena, which, however, are in accordance with the complex behavior of simple systems studied by Stephen Wolfram. For example, two candidates for prefix-suffix pairs of image words that look just similar, may yield 1000-fold running times when searching through all possibilities for proper infixes!

We also discuss some open problems related to pattern avoidance and show tentative examples of certain combined abelian patterns where the number of words avoiding these patterns seems to vary in a complicated way.

Rafal Kicinger
George Mason University

The goal of this project was to introduce NKS to engineering design problems and estimate a true potential of this approach. It was an initial step in exploring the world of simple programs for engineering design applications as well as introducing a novel methodology presented in Wolfram’s A New Kind of Science.  The motivation for this research was based on the fact that even designers of complex and sophisticated engineering systems (bridges, tall buildings, space structures, etc.) use only a relatively small set of design/decision rules to develop design concepts. Hence, it is plausible that even very complex designs of engineering systems can be modeled using simple programs like cellular automata (CA).

The initial exploration of the space of simple programs has been focused on one-dimensional CA (1D CA) and two-dimensional CA (2D CA). 1D CA have been used to generate design concepts of wind bracing systems in tall buildings. These experiments were performed using both elementary CA where two possible types of bracings were used and more complex 1D CA involving 7 possible types of bracing elements. In another set of experiments 2D CA were used. Several types of totalistic 2D CA were studied, including Moore neighborhood and von Neumann neighborhood.  The fitness of the generated design concepts was determined based on rigidity of the structural systems and measured by their maximum deflection.

Results of the conducted experiments have shown that CA can generate interesting structural shaping patterns. They included both traditionally known patterns for this class of buildings like vertical and horizontal trusses, but also some novel arrangements of wind bracings characterized by high fitness values. The best results in the reported experiments were obtained using 1D CA.  2D CA also have the potential of producing interesting structural patterns but the search space is vastly larger compared to the 1D CA case and a much larger number of experiments is necessary.

Ilan R. Kirsch
National Cancer Institute

Todd Rowland
Wolfram Research

Some fundamental insights are needed to begin the transition of biomedical opinion of NKS from disinterest to application and utilization. Subjectively, it would seem that the application of NKS to biological systems that are already recognized as models of other physical systems while interesting in their own right, represent more variations on a theme than convincing demonstrations of inroads of NKS into virgin territory. It is in this context that consideration of the contribution of NKS to more fundamental principles in biology becomes critical.

Cancer and cancer biology represent vital systems for exploring the potential of NKS to illuminate biology. In many respects, cancer, the disruption and dysregulation of normal growth, development, and differentiation is a microcosm of biology itself. Cancer is sometimes portrayed as a complex disease that no simple approach can encompass, prevent, or cure. On the other hand, NKS suggests that there could be some simple underlying behavior, or possibly instead that some simple model could capture the essential features of cancer.

If we already knew the deterministic rule for the development of cancer (if one exists) then we could employ it in the development of a pattern whose cancer predictive capability could be tested. In the absence of that knowledge, a possible approach is to model cancer by creating an image consistent (hopefully) with the evolution of a definitive or probabilistic cellular automata and then try to work from that picture back to the relevant condition and rule that generated it. More to the point, the idea would be to create a rough picture which captures some essential elements of the development of a primary tumor within a particular cell lineage. It would send out exploratory representatives across the field of the pattern.  Sooner or later one of those emissaries that has landed in another region triggers a clonal proliferation. It’s easy to visualize this occurring on a kind of CA background, for example an evolution of rule 110 that has distinct pattern elements with transitional zones between them.  One scenario for the cause of clonal proliferation is a local change of the rule dictated by the background patterns and the underlying rule.  In the case of a deterministic underlying rule, it would have to be a rare configuration, while in the case of a probabilistic rule it could also be unlikely.

Once candidate patterns have been identified, will some initial condition and rule provide distinctive insight into the process of malignant transformation? Only doing the experiment and trying to interpret the result will answer that question.

Benjamin Hsuehyung Koo 
Massachusetts Institute of Technology

Ed Crawley
Massachusetts Institute of Technology

Designing complex engineering systems such as spacecraft and automobiles presents tremendous technical and managerial challenges. These challenges mostly emerge from the overwhelming interactions between physical subsystems and information flow between humans and machines. To orchestrate the interactive complexity of large-scale engineering systems, the designers must cope with a large number of variables and a set of complex rules that govern the interactions among them.

These complications make it extremely difficult to construct models within a reasonable amount of time even if component-level modeling knowledge is available. This talk illustrates an NKS-inspired modeling approach to reduce the amount of modeling effort for complex systems. Specifically, our research indicates that NKS approaches can be applied to represent both simple and complex subsystems in a holistic manner. Instead of using binary variables connected in a one-dimensional topology, we found that complex engineering systems can be modeled as a network of qualitative and quantitative variables with a simple rule-based NKS-inspired engine, to perform informative calculation for its designers.

To illustrate the practical value of this NKS-inspired system modeling tool, we applied this tool to study    NASA’s  Apollo program, and presented our NKS-inspired approach to the key architects and engineers of the Apollo program. The original architects and engineers of the Apollo program responded with highly positive feedback and articulated a series of potential applications of this approach to their project.

In our presentation, we will briefly present the architecture of our calculation engine, modeling tool, and explain the scalability and utility of NKS in designing complex engineering systems.

Jiri Kroc
University of West Bohemia
Helsinki School of Economics

The main goal of this work is to show on a simple periodic case—and easy to simulate—that there exists a class of cellular automata, possibly deterministic, enabling us to effectively perform the coloring of tiled planes. Similar algorithms—where determinism is in question—could be applied to the three-neighbor case on square grids and to aperiodic or quasiperiodic three-neighbor tilings, as for example, the Penrose tiling.

A rule which performs a coloring of tiles ensures that no two neighboring tiles have the same color. A 2D deterministic cellular automaton is defined and performs a two-coloring of squares in the plane using self-organization.

Anti-phase separation boundaries lie between two regions, inside of which all tiles are correctly colored with respect to each other, but the boundary itself is out of the order. They naturally emerge from random and non-random initial conditions, and their presence could lead to more than two times longer the total simulation time.

Appearance of such anti-phase separation borders could be protected by use of a special initial condition consisting of one seed—located in the left-lower corner in our case. Seed has one color and is immersed into the homogeneous ‘sea’ of cells having the opposite color. This initial condition is in the perfect consistence with the rule. One has to keep in mind that both the rule and initial condition are equally important in order to get an effective, correct, and fast solution.

Olu Lafe
QuickCAT Technologies

A class of cellular automata described by a concise rule system known as W-Rule will be presented. We will show how W-Rule is a compact way of representing multi-state and multi-dimensional cellular automata in any arbitrary neighborhood configuration and size. Special properties such as periodicity and reversibility will be examined. We will discuss the relationship between the period and the parameters characterizing the cellular automata. We conclude by presenting the parameter determination technique and showcase the applicability of W-Rule to data encryption.

Corey Lofdahl
Science Applications International Corporation

The social sciences provide a rich repository for open, interesting, and unsolved questions that can benefit from the application of complex systems research techniques. After “solving” a problem though, researchers must present their results, which is not as straightforward as it might at first appear. This study describes lessons learned presenting complex systems results to an economics audience during the publication of Lofdahl (2002a). The study is organized by four lessons: 1) size your model appropriately, 2) build the intuition of your reader, 3) do your homework, and 4) choose your audience wisely. The study concludes with six open economics questions awaiting the attention of complexity researchers.

Christopher Maes
Massachusetts Institute of Technology

Iterated maps operating on x and the representation of x in base b are studied. Particular attention is paid to the reversal addition map given by (Subscript[x, n+1]) = (Subscript[x, n]) + R((Subscript[x, n]), b) (where R(y, b) is the reversal of y in base b). Qualitiative classes of behavior similar to those in cellular automata are found in successive terms in the sequence. An algorithm for classifying unique sequences and determining the behavior of a sequence is presented. All simple maps are enumerated and those maps which produce complex behavior are found. Carry propagation and dependence on initial conditions are analyzed. A conjecture on maps in the form f(x) + R((g(x), b) producing complex and thus universal behavior is presented.

Genáro Juarez Martinez
Universidad Autónoma de Puebla

We will present a procedure for the construction of initial conditions that produce complex behaviors in rule 110. The procedure uses regular expressions that we call phases f{Subscript[i]}_1 By concatenating the regular expressions, all the regularities in each construction are conserved because the constructed initial configuration is another regular expression It offers an alternative method to discover in rule 110 some important phenomenon from cellular automaton theory.Examples of some of the behaviors found are the production of gliders, groups of gliders, meta-gliders, solitons, and the construction of great triangles and other rule 110 objects through collisions, as well as the parts to the cyclic tag system emulation crucial to the only known proof of universality for rule 110.

Katherine Rodway McKee
Columbia University

Gautam Dasgupta
Columbia University

The twentieth century has seen an explosion of tourism development, particularly in poor, underdeveloped countries, that has impacted the organizational, cultural, and societal adaptation of the built environment and its population. Many tourist destinations are based in and around sites of cultural and natural heritage. To better enable policy makers in decision-making, risk assessment, and hazard mitigation of world heritage social scientists have been acquiring information concerning agents of change and dynamics of human behavior that effect successful sustainable development in these areas.

Through the use of spatial analysis and environmental and social dynamics models this presentation seeks to build an NKS framework and analytical methodology of tourism development as it relates to land use/cover changes over time. Our goal here is to gain a better understanding of the causes and ramifications of change to cultural and natural heritage resources and their surroundings.

Many heritage sites are threatened by lack of maintenance, security issues such as looting of significant elements; encroachment of vegetation; and exposure of the structure and materials. Their regions are subject to mass tourism and related over-development; problems in water resources and hydrological cycles, deforestation, food supply, and disease. Significant changes in land use and land cover in these regions have, and will, disastrously impact both the built and natural environments.

However, we must realize that there will be growth or change factors contributing to a system of habitation within these regions, and, as the economy of these regions rely more and more on tourism, that the heritage resources, which are the income generators, are not destroyed and vanquished like the former societies. It is a matter of conserving a “way of life” for the regional stakeholders—the local people and representatives of our common heritage.

Planning and management for sustainable development at heritage sites has two parts.  The first involves a research methodology, which utilizes broad-scale spatial analysis to identify the causes and effects of human activity over time, make inferences on the mechanisms of cultural change within a region, and understand the dynamics of contemporary development in and around the areas, enabling greater mitigation and management. The second consists of mathematical modeling, which enables quantitative analysis of qualitative data and visualization of future consequences of environmental and man-made threats.

In this presentation we demonstrate how methodology and modeling can be used as effective tools for decision-making at some of the most dynamic and rapidly evolving places in the world.

Frederico Meinberg 
Freiburg University

My work in the NKS Summer School 2003 was concerned with so-called symbolic systems. Wolfram (2002) presents symbolic systems as one class of simple programs, besides cellular automata, Turing machines, register machines, and others. The evolution of a symbolic system consists in the application of a set of one or more rules of the form lhs -> rhs to an initial expression. Following the directions set by Wolfram (2002), the simplest forms of symbolic systems were investigated, in search for the threshold of complex behavior. The parameters investigated were number of rules, number of operators, and the size of lhs and rhs, as well as the size of the initial conditions. It was found that the threshold of complexity is reached with rather small sizes of rules and initial conditions. Other issues dealt with were how to visualize symbolic systems and how the evaluation scheme used to apply the rules affects the evolution of the system.

Philipp Michel
Yale University

While machine learning systems such as artificial neural networks have been employed in a wide range of application domains in the past, their dynamics have often evaded traditional methods of analysis. Throughout this project, the author took an NKS-inspired approach of experimentation and graphical exploration towards the analysis of learning methods, with particular emphasis on the visual properties of their basins of attraction. First, a traditional example of the phenomenon of basins of attraction, Newton’s root finding method, was considered. The aim was to seek complex and interesting behavior through directed experiments. Next, attractors in Hopfield neural networks were investigated through visualization. Finally, the same methodology was applied to search for elementary classification behavior in simple NKS-style sequential substitution systems.

Victor G. Mossotti 
U.S. Geological Survey

Deposition and erosion patterns are observed across an extremely wide range of scale on surfaces of geological and ecological interest, as well as on surfaces of cultural importance. The purpose of this work is to craft a framework for the design of automata-based simulations of deposition and erosion processes. The surfaces studied in this work, mainly calcareous stone buildings and monuments, served as surrogate substrates for a wide variety of naturally occurring catchments found in geological settings, albeit on a lesser scale.

In natural settings, depositional and erosional processes generally evolve over periods that include many wet-dry cycles. Under the varying conditions of wet-dry cycling, the rate-limiting path in a system of connected processes can switch with time among a set of alternative processes. The modeling challenge is compounded by the fact that the physicochemical landscape continuously changes throughout wet-dry cycling in response to the integrated consequences of ongoing depositional and erosional processes. We have adopted a modeling approach based on the observation that all types of depositional systems can exhibit spatially fractal zones within their full-scale patterns. Such observations support the assumption that control of deposition and erosion dynamics is exercised at the smallest scale of the measurement. In this model, we assume that local interactions at the scale defined by the measurement resolution drive the evolution of the observed depositional and erosional dynamics at all scales. It follows that there are two closely coupled parts to modeling the dynamics of such a system. The first part, which is discussed in this paper, is to model depositional and erosional dynamics accommodated by separate resolution elements; the second part, and probably the most challenging, is to model interactions between the parcels of material forming the pattern mosaic.

The mosaic model provides perspective on links between primary delivery processes, variables endogenous to the substrate, and deposition and release processes, as well as on conditions controlling short-range and long-range correlations in patterns. As a consequence of feedback loops and competitive processes, the model predicts that 1) relationships between measurable properties of the system are generally nonlinear, and 2) soiling pattern evolution may follow a trajectory that is hypersensitive to the system variables. In general, the mosaic model shows that short-term experiments or observations on isolated system components generally should be interpreted with caution when used for the prediction of long term phenomena. This is because significant feedback loops may be decoupled from the system when observations are made over a limited range of scale in space and time. In addition, nonlinear controls on pattern evolution need to be taken into account in modeling future states of the system, whether the decisive variable is the sedimentation load in a benthic system or the time-to-remediation for a cultural monument. Lastly, the sensitive dependence of pattern evolution on the initial state of the system may result in outcomes that are not reproducible under virtually identical conditions.

Andrew Musselman 
Central Washington University

In his book A New Kind of Science, Stephen Wolfram discusses the appearance of random behavior in nature and in the output of various simple programs. He describes three mechanisms for generation of such randomness and presents examples of each [NKS, p. 299-326].

We present work done in a project to study the existence and nature of random behavior present in the output of cellular automata and related systems. We have implemented in Mathematica code a suite of statistical tests for analyzing the random behavior in a sequence of binary data. These tests were taken from the Random Number Generator Test Suite developed by the National Institute of Standards and Technology [NIST]. We have applied these tests to data sets created from the output of various cellular automata, e.g., the center line of the output of rule 30 starting with a single black cell (This data set is, as expected, judged random by all tests we have run.) We have also applied the tests to other subsets of the output set: other vertical slices, horizontal slices, and various diagonals. We have also tested output sets resulting from running CAs starting with randomly chosen initial conditions and also from adding random noise to the normal output of a CA. We will present a selection of these data sets and the results of the statistical analyses.

[NKS] Wolfram, Stephen, A New Kind of Science, Wolfram-Media, Inc., 2002.

[NIST] Ruhkin, Andrew, et al, “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications,” National Institute of Standards and Technology (NIST Special Publication 800-22), May, 2001.

Pedro Paulo Balbi de Oliveira 
Mackenzie University

A widely studied computational problem in the context of cellular automata (CAs) is the so-called Density Classification Task (DCT, for short). In its standard formulation it states that a binary, one-dimensional CA has to converge to a final configuration of all cells in state 1, when the initial configuration has more 1s than 0s, and to a configuration of all 0s, whenever the initial configuration has more 0s than 1s. Although the DCT was proposed in 1978 [Gacs, Kurdyumov and Levin, 1978], it was not until 1995 that the solution of the problem, as formulated, was proven not to be possible [Land and Belew, 1995].

Before the original proof was derived a few research groups were trying to find a rule that could solve the DCT. However, with such a possibility precluded the search shifted towards looking for the rule that could solve the DCT as perfectly as possible. Using different search techniques, mostly evolutionary computation-based methods, various groups have put their methods to test, and over time good rules have been found. For historical reasons, the search methods employed have been scanning the huge radius 3, 2-state CA space, the best rule found so far being due to Juillé and Pollack [1998], with a correct classification score of about 86%. The fact is that regardless of empirical and analytical efforts carried out during the last years, the best imperfect rule for the DCT remains unknown.

Our concern herein is on ways that might help a search for better imperfect rules for the DCT than those currently known. And this is done by trying to answer the following questions: could good, known DCT rules be used as an indication of the most promising regions of the search space?; and, could conservative rules in the search space provide an indication of regions to be avoided during the search? These questions are addressed by relying on analyses of good, known rules from radius 3 space and on a search carried out in the radius 2 space.

References: 
[Capcarrère and Sipper, 2001] M.S. Capcarrère and M. Sipper. “Necessary conditions for density classification by cellular automata.” Physical Review E, 64(3):036113/1-036113/4, 2001. 

[Fuks, 2000] H. Fuks. “A class of cellular automata equivalent to deterministic particle systems.” In: S. Feng, A.T. Lawniczak and S.R.S. Varadhan, eds. Hydrodynamic limits and related topics, Amer. Math. Soc., Providence, RI, USA, 57-69, 2000. 

[Gacs, Kurdyumov and Levin, 1978] P. Gacs, G.L. Kurdyumov and L.A. Levin. Problemy Peredachi. Informatsii, 14:92-98, 1978. 

[Juillé and Pollack, 1998] H. Juillé and J.B. Pollack. “Coevolving the ‘ideal’ trainer: Application to the discovery of cellular automata rules.” In: J.R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D.B. Fogel, M.H. Garzon, D.E. Goldberg, H. Iba and R.L. Riolo (eds.). Genetic Programming 1998: Proceedings of the Third Annual Conference, San Francisco, CA: Morgan Kaufmann, 1998. 

[Land and Belew, 1995] M.W.S. Land and R.K. Belew. “No two-state CA for density classification exists”. Physical Review Letters, 74(25):5148-51, 1995.

Ed Pegg Jr
Wolfram Research

Using the set of symbols {1, ×, +} and parentheses, how many 1’s does it take to represent 23?  It turns out that eleven are needed. Surprisingly, the number 27 requires only nine.
23 = (1+1+1) * ((1+1) * (1+1+1)+1) + 1 + 1
27 = (1+1+1) * (1+1+1) * (1+1+1)

This topic was discussed on page 916 of A New Kind of Science.  Since publication of NKS, a long-standing conjecture for this problem was disproved via Mathematica code.  That code and other programming tricks will be shown, along with relevant online databases.  The whole problem will then be expanded into the realm of complex numbers, a topic that apparently hasn’t been researched.

Samuel Penchas 
Hadassah University Hospital

Health care systems (HCS) are complex systems with many independent agents each interacting with the others, occasionally inducing changes in some, and creating complex adaptive systems (CAS) containing emergent properties potential. Amongst independent agents in HCS are language, structure, logic, and social order. Each is fraught with fundamental problems, leading to famous paradoxes. Some of these parameters are initial conditions in CAS, which can be, but do not have to be, sensitive to changes in initial conditions leading to future significant effects. It is still impossible to predict the appearance of emergent properties from independent agent behavior, and evolving HCS can thus turn undesirable and fail. Much of all of this applies to other social systems.

However, there are systems with foreseeable behavior: uniform, repetitive, and nested ones. These are simple systems with reducible computations for predicting their future development. In HCS, one needs to reduce unpredictable developmental failure by emulating such simple systems through the implementation of their basic qualities.

Richard Phillips 
Wolfram Research

Even some of the simplest cellular automaton rules can produce patterns as intricate as any pattern we expect to be possible in nature. Here we look at how the overall shapes produced by these simple rules grow. There are many possibilities besides the familiar triangular shape.

We include investigations of many initial states, such as those that are made by changing a small group of cells on a periodic background pattern.  We will also look at the more specific question of what boundary growths are possible in theory, and find some useful answers.

Carlos E. Puente
Rice University School of Architecture

The construction of a multitude of interesting patterns, defined as projections of simple multifractal measures supported by fractal interpolating functions, is reviewed. It is illustrated, via a variety of examples, how these ideas bring forth a new Platonic vision to address the complexity of some of nature’s tangled patterns over one, two, and three dimensions, including relevant applications to geophysics: (a) rainfall time series and fields, (b) river network’s width functions, (c) two and three-dimensional contaminant plumes within porous medium, and (d) general “chaotic” and “stochastic” signals with diverse power-law power spectra, as found on several applications. Also reviewed is a universal connection between arbitrary diffuse measures and the univariate and bivariate Gaussian distributions, as found when the fractal interpolating functions become plane- and space-.lling, respectively. It is explained how the latter yields an innate class of two-dimensional symmetric crystalline sets (Borges’ alephs) making up exotic kaleidoscopes of arbitrary symmetries, that decompose the bivariate Gaussian distribution in nontrivial ways. It is shown that such mathematical designs include the structure of natural ice crystals and the rosette structure of relevant biochemical units, including even life’s own DNA.

Tilman Rassy 
Berlin University of Technology

The aim of this work is to validate Boltzmann’s ideas concerning the derivation of “irreversible” kinetic equations from “reversible” mechanical laws by reformulating them in a rigorous, modern mathematical context and applying them to a simple mechanical model.

First, Boltzmann’s ideas, developed as a reaction to the objections raised against the Boltzmann equation, are carefully restated in a modern way. It turns out that Boltzmann’s view was far more “mechanical” than the perspectives usually adopted in the later literature. In particular, “molecular chaos”—a crucial argument in the derivation of the Boltzmann equation—was a property of single microstates (not, e.g., of a probability measure) and therefore a purely mechanical term. Probability only entered the theory in a way that does not question its basically mechanical nature. Unfortunately, Boltzmann was not able to work out his ideas in the necessary rigor (which is probably impossible for real mechanical systems because of their complexity). Therefore, the power of persuasion of his ideas has been diminished.

In the second part of the work, a very simple model system is constructed. It shows a “chemical reaction” for which an irreversible kinetic equation can be obtained in a heuristic way, completely analogous to the derivation of the Boltzmann equation. Since the underlying microscopic dynamics is reversible, we are in the same dilemma as Boltzmann was. Then, Boltzmann’s ideas are applied, but in a mathematically rigorous manner. In particular, “molecular chaos” is exactly defined as a property of single microstates. As long as the microstate possesses this property, the kinetic equation holds. It can be shown that—with respect to a reasonable probability measure—the microstate is and will remain “molecular chaotic” with probability one. As a consequence, the kinetic equation holds with probability one.

Finally, the implications of the work are discussed. The opinion is given that the work contributes to the clarification of Boltzmann’s ideas and may be used as a pedagogical attempt to teach these ideas.

Jamie Raymond
Northeastern University

The goal of the research I will present in my talk is to help high school or beginning college students who may have little programming experience do NKS experiments. This research stems out of my previous work as a high school science teacher and my current work as a researcher in programming languages and programming pedagogy. Specifically I am interested in extending my work with the TeachScheme project, which tries to foster introductory programming education through curricula focused on the program design process (presented in the book How to Design Programs), pedagogical programming language levels, and a student-friendly programming environment, to the domain of NKS.

I will present preliminary results related to three questions posed in my research. First, what might make good NKS experimental design methodology that can be summarized on a notecard, similar in flavor to the scientific method presented in introductory science courses? Second, what new NKS-specific programming languages, embedded in a general purpose language, might be developed that will simplify both generating and analyzing data from NKS experiments, while meshing well with the TeachScheme approach? Third, how can the tenets of the TeachScheme program design methodology transfer to Mathematica, the lingua franca of NKS?

William P. Reinhardt
University of Washington, Seattle

The College of Arts and Sciences at UW has introduced a flock (ca 40) of 4 week intensive, self-contained, and for credit seminar courses, for groups of 20-24 students new to the University. These Discovery Seminars covered topics ranging from “Sex in Seattle” to “Scientific Modeling using Cellular Automata,” this latter being my NKS-based course. The seminars were taught just before these students would normally enroll for a full fall first year course load. The seminars serve two purposes:  they may be imaginative and interdisciplinary, as they are not necessarily part of “departmental” offerings; and, they serve as an excellent and focused way of introducing new freshmen/women to university level studies and expectations.  Students taking the Discovery Seminars out performed their peers in the fall quarter, even after corrections for their “expected” success are factored in.  NKS provided a wonderful and rewarding curriculum for a computer lab-based seminar taught for the first time in the summer of 2003. Essentially all of the NKS text, plus a lot of Mathematica, was covered, except material on general relativity and quantum mechanics. Students were presented with modeling problems and also with many “open and initially rather poorly defined” conceptual questions with which they needed to grapple by choosing and creating structures within which answers “might make sense.” Almost all were able to learn to do so within the context of the A New Kind of Science Explorer CD-ROM programs.  A typical response was, “wow, high school was never like this!”

Eric Rowland 
Rutgers University

In some sense, one can measure the complexity of a sequence {a[n]} of integers by examining the sequence {Mod[a[n],n]} obtained by reducing the nth term modulo n. When a[n] is a polynomial, the sequence {Mod[a[n],n]} is quite simple—it is constant for sufficiently large n. But even slightly less pedestrian sequences give rise to complex behavior. The familiar Fibonacci numbers and the binomial coefficients both result in tantalizing sequences when reduced termwise modulo n. I will discuss the patterns that can be seen in these sequences and how they suggest (as yet unknown) computationally reduced formulas for Mod[Fibonacci[n],n] and Mod[Binomial[n,m],n].

Todd Rowland
Wolfram Research

Teaching NKS should be simple. Not only is the material accessible, but it is also engaging on several different levels. Even young children starting school can do the basic experiments. Older kids studying simple rules can learn to think rigorously and critically, as well as take on challenging problems.

I will survey an alpha version of the educational materials we at Wolfram Research have been making to introduce NKS. There will be a core two-week course geared toward high school students, which could also be used at the college level. There will also be a set of lessons which can lead to more open-ended instruction, treating some material more deeply or posing challenging problems. In addition, we will make lessons geared to the elementary and middle school levels.

I will also talk about the process of learning about NKS, which is related to making original NKS discoveries. The science of NKS has some things to say about learning and knowledge, at least in the context of studying simple programs.

There are definite phases of understanding, and we are concentrating on the introductory levels with these materials. We hope that these materials will be easily understood by teachers, and that they will find them flexible enough to fit in with their own style and philosophy of  teaching.

Todd Rowland
Wolfram Research

The summer school is a unique opportunity for students to get started doing NKS research.  It lasts for 3 weeks, and, at least for its first two years, is located at Brown University.  We will talk about why we do it, how it is structured, what we do with the students, what students have done with their projects, and what we expect from applicants.

Jose I. Sanchez
Columbia University

Gautam Dasgupta
Columbia University

Architectural form has traditionally been implemented neglecting potential mathematical relations within the program of a building. With the advent of advanced time-based computer modeling techniques, architects are able to implement quantifiable data into the architectural design process. Traditional line sketches can be generated by using the inherent dynamics of the architectural program, which carries the ever-changing programmatic quality of today’s used of residential and commercial buildings.

Michael Schreiber

Proof: A Spencer-Brown form term is equivalent to Wolfram rule 110. This term is a nested form and accepts three inputs. Bit inputs are translated into form versus empty. Computation returns one form output for three form inputs. Decoding returns one for form and zero for empty. All eight possible inputs return like rule 110.

Consequence: A distinction process like form is all you need to compute. A system is equivalent to rule 110 if it can distinguish: more than one is one, but one inside one is none. This is equivalent to DiscreteDelta in Mathematica.

Observations: According to Spencer-Brown a form may recycle output as input. It turns out that this can be used to carry out the addition of bit streams. Neither conventions for translating between form and bit nor conventions about input order are necessary. Such conventions can be accommodated by compositions of transformations. One transformation permutes inputs. The two others switch translations of inputs and outputs. There are 26 characteristic forms. All 256 rule numbers are derived by compositions of the three transforms. Their characteristic letters articulate a palindrome.

Joshua Schwartzstein 
Cornell University

This project investigates the effects of perturbations on elementary one-dimensional cellular automata (CAs). These effects are examined from “a pure NKS,” as well as a social science perspective. In other words, the general evolution of the perturbed CAs is of interest as well as the perturbations’ ability to produce some desired behavior. Perturbed CAs can be viewed as a model of systems affected by policies or control schemes. Through examining such CAs some inferences may be drawn as to the effectiveness and consequences of various types of policies and schemes.

Brian Silverman
Massachusetts Institute of Technology Media Lab

Eric Klopfer
Massachusetts Institute of Technology Teacher Education Program

Bakhtiar Mikhak
Massachusetts Institute of Technology Media Lab

Hal Scheintaub
Governor Dummer Academy

In A New Kind of Science, Wolfram states, “The new kind of science in this book represents a unique educational opportunity. For it touches an immense range of important and compelling everyday phenomena and issues in science, yet to understand its key ideas requires no prior scientific or technical education.”

Our research and development is well aligned with this philosophy. Over the last two decades, we have been developing and studying software and pedagogical approaches that we think have several points of contact with
NKS. In particular, our technologies have enabled students and teachers to engage in rich authentic computationally enabled investigations in experimental mathematics and science. Our work centers around Logo, and the
many related projects that it has spawned and inspired. While there have certainly been challenges, many of these projects have met with a great deal of success in reaching students and educators throughout the world.

During our talk we will present the educational philosophy behind Logo. We will also demonstrate StarLogo, an agent-based modeling system used in high schools, and talk about the issues and challenges involved in getting this kind of technology accepted by schools. We will conclude with a discussion of how the many lessons we have learned are likely to be pertinent to the NKS community as we try to realize the unique educational opportunity that NKS represents.

Bradley L. Sim
University of Ottawa

Frederik P. Agterberg
Geological Survey of Canada

If convection in the earth’s liquid outer core is disrupted by turbulence and begins to behave in a chaotic manner, it may destabilize the Earth’s magnetic field and provide the seeds for kimberlite melts via turbulent jets of core material which invade the lower mantle. These (proto-) melts may then be captured by extreme amplitude solitary nonlinear waves generated through interaction of the outer core surface with the base of the mantle. A pressure differational behind the wave front provides a mechanism for the captured melt to ascend to the upper mantle and crust so quickly that emplacement may indirectly promote a type of impact fracture cone within the relatively brittle crust. These waves are very rare but of finite probability. The assumption of turbulent effects transmission between layers is justified using a simple three-layer liquid model. The core derived melts eventually become frozen in place as localized topographic highs in the Mohorovicic discontinuity, or as deep rooted intrusive events. The intrusions final state composition is a function of melt contamination by two separate sources, the core contaminated mantle base and subducted Archean crust. The mega-wave hypothesis may offer a plausible vehicle for early stage emplacement of kimberlite pipes, carbonates, or orangeite melts and explain the age association of diamondiferous kimberlites with magnetic inversions.

Jeremy Smith

Originally, I was exploring ways of arranging streams of random data into fairly coherent visual landscapes, in order to develop some methods for visually studying non-random data. Almost immediately, I (re)discovered the emergence of complex structures from simple rules or algorithms. The multitude of patterns presented here represent the application of a few simple algorithms (sorting and arranging rules) on streams of random data.

Dag Soeroboe 
University of Bergen, Norway

In my project at NKS Summer School 2003, we considered Cellular Automata (CA) under mathematical constraints derived from the Prisoners’ Dilemma (PD). An algorithm for simulating play between the 256 elementary CA in a round-robin iterated PD tournament was implemented, and the results for each CA were computed and plotted. Results suggested that the CA can be grouped in four categories with respect to outcome under the experimental setup in the study.

It seems to me that more research is needed in order to find out how CA can be applied to the study of rationality paradoxes in useful ways, and I will give a brief outline of some of the philosophical theories and questions I have encountered since NKS Summer School 2003.

Klaus Sutner
Carnegie Mellon University

The existence of intermediate degrees of computability is one of the central results of twentieth century recursion theory (priority method). We will explore the impact of this result on the study of computational properties of CA and reversible CA and show that the classical results carry over, mutatis mutandis, to the realm of CA.

NKS|Online: www.wolframscience.com/nksonline
Oyvind Tafjord
Wolfram Research

Downloadable Programs
Ed Pegg
Wolfram Research

CellularAutomaton
Richard Phillips
Wolfram Research

Automata
Klaus Sutner
Carnegie Mellon University

NKS Community Tools
Ed Pegg
Wolfram Research

NKS Explorer/NKS Explorer: Mathematica Kit
Oyvind Tafjord
Wolfram Research

The NKS Forum: forum.wolframscience.com
Jason Cawley
Wolfram Research

Oyvind Tafjord
Wolfram Research

I will review some of the ideas in A New Kind of Science regarding the abstract nature of space and time. In particular I will talk about the concept of causal networks arising from the evolution of simple rule systems, and how familiar physical concepts, such as special relativity, arise in a natural and fundamental way.

Victor Trafaniuc
Mackenzie University

A finite automaton is a system defined by states and state transitions that creates a network capable of processing strings of symbols of a certain kind, known as regular languages. In [Wolfram, 1994] it has been shown that the set of possible configurations that can appear in the evolution of one-dimensional cellular automata, at any given time step, can be described by finite automata. In the face of that, one can think of the regular language complexity of a cellular automaton in terms of the number of states and state transition of the finite automaton that characterizes all possible configurations at a given time step.

In [Wolfram, 2002], some functions implemented in Mathematica are presented (NetCAStep, TrimNet, and MinNet) that yield those finite automata, for any given time step, of any one-dimensional cellular automaton rule. After we made an adequate transformation of the output of these functions, from their original list representation to an explicit graph, we went about studying the regular language complexity of the resulting finite automata for all elementary cellular automata rules, that is, the one-dimensional celular automata with nearest neighbours and two states per cell.

By comparing the graphs generated at different time steps, it has been possible to find common structures and clear growth patterns between them for several rules. This was achieved with the help of an algorithm we developed that identifies the rules in which a growth pattern becomes evident when two subsequent time steps are compared and by analyzing them at that point. While the regular language complexity of many rules agreed with the original findings in [Wolfram, 1994], a few have slightly distinct values, a deviation that is in need of an explanation. Above all, out of the analyses carried out, explicit formulae were derived for the regular language complexity of various elementary rules for which no explicit formulation was apparently available so far.

References:
[Wolfram, 1994] S. Wolfram. “Computation theory of cellular automata,” Cellular automata and Complexity:Collected Papers, Addison-Wesley, pp.159-209, 1994.
[Wolfram, 2002] S. Wolfram. A New Kind of Science, Wolfram Media, 2002.

Stephen Wolfram
Wolfram Research

Stephen Wolfram
Wolfram Research

See first hand what's involved in doing NKS research. This will be an unscripted session in which Stephen Wolfram will carry out a live experiment on some NKS topic. Get insight into how to set up your own experiments, how to pick NKS research directions, as well as lots of tips and tricks. Audience participation will be welcome. At NKS 2003 the live experiment was an exciting ride, with an interesting small result on cellular automata discovered in real time. At the NKS 2004 live computer experiment anything could happen...

Stephen Wolfram
Wolfram Research

A chance for lively in-depth Q&A with Stephen Wolfram, sure to range over a broad array of topics. Ask about the basic science of NKS, its applications and implications, as well as future initiatives and the organizational structure of NKS.

Stephen Wolfram
Wolfram Research

Hear the founder's developing vision for NKS, and get a first-hand account of the latest ideas about the intellectual structure and promise of NKS. Hear about some exciting new initiatives and plans underway in research, technology, and education with NKS. Find out about important emerging opportunities made possible by NKS in science, technology, and business. The keynote is expected to feature some significant NKS-related announcements.

Wolfram Science Group

Staffed by members of the Stephen Wolfram Science Group, the NKS Computer Experiments Clinic is a place where one can get help with practical and conceptual issues relating to NKS-style computer experiments—or simply be an observer in a collegial environment of discovery. We will engage with all comers, helping with both pure and applied NKS projects. While we can try to narrow a problem so that it can be attacked using NKS methods, it is obviously better to bring a specific problem.

If you have some files on your computer which are relevant to your problem, e.g. a PDF or a Mathematica notebook, and you think it will speed up the process, then you can upload the file so we will be able to access it during the clinic.  Please go to upload.wolfram.com and follow the instructions. Under Recipient, enter kovasb.

Wolfram Science Group

Members of the Wolfram Science Group will lead a lively discussion of media coverage, reviews, and other responses to A NEW KIND OF SCIENCE. What's been gotten right, what's been gotten wrong, what's been downright stupid? What's behind common misunderstandings and criticisms? Discuss your favorite---or least favorite---reviews of NKS. How does what's happening with NKS compare with historical paradigm shifts?

Wendy Zhang
Indiana University 

Stuart A. Newman
New York Medical College 

James A. Glazier
Indiana University

Substitution models are iterative procedures for developing complex structures. While substitution models are common in bioinformatics analyses of protein structure, we have found substitution models are also useful for describing development at the cellular level, agreeing well with experimental data on developmental systems, including cell division, differentiation, cell-cell interactions, and cell movement in response to external fields. During development of the vertebrate limb, spatiotemporally regulated condensation of mesenchymal cells, followed by chondrogenesis, leads to a pattern of skeletal elements. We have devised a three-dimensional substitution model by simple rules to describe limb growth, cell differentiation, and cartilage pattern formation, incorporating mechanical constraints. We have validated the model by predicting the cell behavior and comparing it to experimental data.

Thomas Zheng 
University of California, San Diego

Transforms are important tools for scientists and engineers studying complexity. The author postulates that complexity can be manipulated through transforms, i.e. reduced or multiplied.  In this topic, one particular type of transform, Discrete Orthogonal Transform (DOT), is discussed.  In particular, the author draws the systematic connection between DOT and CAs.  Starting by looking at the Fast Fourier Transform (FFT) algorithm, the author demonstrates that many other Discrete Orthongonal Transforms can be implemented by a two-stage cellular automata consisting of an additive CA and a reversible CA.  Extensions to Generalized Transform (GT) using Cellular Automata will also be discussed.