The Dark Side of Hardware Upgrade Forum

Cellular automata (CA) are a class of spatially and temporally discrete, deterministic mathematical systems characterized by local interaction and an inherently parallel form of evolution.

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off" (in contrast to a coupled map lattice).

[...]In the strongest possible
terms, the long time behavior of computationally universal dynamical systems can
be obtained only by direct simulation. No general predictive procedure is possible,
even in principle. This implies, for example, that for systems such as von Neumann’s
self-reproducing automaton, there can neither be an analytical expression that ex-
actly describes its asymptotic behavior nor an equation that defines the long-term
behavior that itself can be soIved in a time Iess than it would take the system to
evolve (modulo a polynomial function of the number of iteration steps necessary for
it to reach its final state). All such computationally irreducible systems share the
property that their own evolution effectively defines the most efficient simulation of
their behavior.

CA as 0rigin.al Models of Fundamental Physics
CA allow studies of radically new discrete dynamical approaches to microscopic
physics, exploring the possibility that Iiature locally and digitally processes its own
future states. The entire last chapter of this book is devoted to a prolonged dis-
cussion of such potentially ground breaking niotiels of physics. Using the fact that
computationally universal systems are capable of arbitrarily complicated behavior
(in the sense that they can mimic any computation performed by a conventional
computer), the idea is to construct fundamcntally discrete field theories to compete
with existing continuous models. T h e emphasis in this class of models is ernphati-
cally not to construct a lattice-gauge-like theory; rather, in the same way as lattice-
gas CA successfully reproduce continuous fluid flow despite never having heard of
the Navier-Stokes equations, so the hope is to abstract a set of microphysical laws
that reproduce known behavior on the macro scale. A number of interesting ideas
have recently been explored. Fredkin [freclkin93]has arguably gone to the furthest
extreme by asserting that the universe is, a.t its core, a CA! We will offer a few of
our own speculations on this subject in the last chapter.

What is remarkable about this very simple appearing n h e is that one can show
that it is capable of universal computation. This means that with a proper selection
of initial conditions (i.e. the initial distribution of “live” and “dead” cells), Life can
be turned into a general piirposr: computer. This fact fundamentally limits the
overall predictability of Life’s behavior.
The well known Halting Theorem, for example, asserts that there cannot exist
a general algorithm for predicting when a computer will lialt its execution of a
given program [garey79]. Given that Life is a universal computer ~- so that the
Halting Theorem applies - this means that one cannot, in general, predict whether
a particular starting configuration of live and dead cells will eventually die out.
No shortcut, is possible, even in principle. The best one can do is to sit back and
patiently await Life’s own final outcome.
Put another way, this means that if you want to predict Life’s long-term be-
havior with another “model” or by using, say, a partial differential equation, you
are doomed to fail from the outset because its long-term behavior is effectively un-
predictable. Life - like all computationally universal systems - defines the most
efficient simulation of its own behavior.

spero sia leggibile

la parte più leggibile è il codice C (ed è identato da culo)

Prego?

Ah, comunque ci ho messo due ore per scriverlo. Non riuscivo a correggere gli errori quando mi sono accorto di avere dimenticato di inserire la funzione main

Metterci uno switch - case faceva schifo?

Dal punto di vista dell'efficenza è esattamente =

Aldin, a volte vorrei avere il tuo tempo libero.

1.3 Outline of Book
The remainder of the book is divided into eleven largely self-contained chapters.
Chapter 2 introduces some basic mathematical formalism that will be used through-
out the book, including set theory, information theory, graph theory, groups, rings
and field theory, and abstract automata. It concludes with a preliminary mathe-
matical discussion of one and two dimensional CA.
Chapter 3 provides a phenomenological introduction to generic CA. The narra-
tive includes both a mathematical description of one, two and three dimensional CA
along with guided-tour through a graphics-gallery of typical space-time patterns.
Simple ways of parameterizing the space of CA rules are described, and a sketch
of the proof of the computational universality of Conway's famous two-dimensional
Life-rule is also provided.
Chapter 4 covers much of the same ground as chapter 3 but from a more formal
dynamical systems theory approach. The discrete CA world is examined in the
context of what is known about the behavior of continuous dynamical systems, and
a number of important methodological tools developed by dynamical systems theory
(i.e. Lyapunov exponents, invariant measures, and various measures of entropy and Outline of Book 19
dimension) are used to characterize the behavior of simple CA systems.
Chapter 5 provides some examples of purely analytical tools useful for describing
CA. It discusses methods of inferring cycle-state structure from global eigenvalue
spectra, the enumeration of limit cycles, the use of shift transformations, local
structure theory, and Lyapunov functions. Some preliminary research on linking
CA behavior with the topological characteristics of the underlying lattice is also
described.
Chapter 6 is a short primer on CA and language theory, and provides a ba-
sic discussion of formal language theory, the relationship between CA and formal
language theory, power spectra of regular languages and reversible computation.
Chapter 7 discusses a variety of topics all of which are related to the class of
probabilistic CA (PCA); i.e. CA that involve some elements of probability in their
state and/or time-evolution. The chapter begins with a physicist’s overview of crit-
ical phenomena. Later sections include discussions of the equivalence between PCA
and spin models, the critical behavior of PCA, mean-field theory, CA siniulation of
conventional spin models and a stochastic version of Conway’s Life rule.
Chapter 8 describes a number of generalized CA models, including reversible
CA, coupled-map latt,ices, quantum CA, reaction-diffiision models, inimunologically
motivated CA models, random Boolean networks, smdpile models (in the context of
self-organized criticality), structurally dynamic CA (in which the tcmporal evolution
of the value of individual sites of a lattice are tlynaxnically linked to an evolving
lattice structure), and simple CA models of cornbat.
Chapter 9 provides an introductory discussion of & research area that is rapidly
growing in importance: lattice gases. Lattice gases, which are discretized models
of continuous fluids, represent an early success of CA rnodeling techniques. The
chapter begins with a short primer on continuum fluid dynamics and proceeds with
a discussion of CA lattice gas models. One of the most important results is the
observation that, under certain constraints, the macroscopic behavior of CA models
exactly reproduces that predicted by the Navier-Stokes equations.
Chapter 10 covers another important field with a great overlap with CA: neural
networks. Beginning with a short historical survey of what is really an independent
field, chapter 10 discusses the Hopfield model, stochastic nets, Boltzman machines,
arid multi-layered perceptrons.
Chapter 11 contains a very brief introduction to what is rapidly becoming one
of the central research areas in complex systems theory; namely, artifical-life (AL).
Owing its origins to von NeumaIin’s early explorations in self-reproducing automata,
AL has blossomed in the last decade from consisting of a few toy worlds hardly more
sophisticated than Conway’s Life-rule universe to intricately rendered 3D artificial
universes populated with interacting creatures undergoing an open-ended evolution.
Topics include a brief survey of von Neumann’s original work, Lindenmeyer systems,
Langton’s vants model, a short primer on genetic algorithms. The chapter concludes
with a discussion of an artificial-life-like mobile CA model of land warfare.
The last chapter is a broad survey of a speculative proposition that CA just
might one day prove to be even more profound in what they say about how our
universe is organized than has heretofore been appreciated. The essence of the proposition, borrowed from rniisirigs b,y Feynnian [fcyii82], Fredkin [fredkingo], Min-
sky [minsky82], Wheeler [wheel901 and others, is that the universe is fundamentally
discrete and obeys, at its core, a simple CA-like dyrianiics. Tlius begin some final
musings and R perhaps a glimpsc of a new cosinogmy!
Appendix A providcs a brief description of several existiiig hardware arid soft-
ware tools designed for CA research. Appendix B contains a useful list of CA arid
inore general coniplcxity-relatctl inforniation soiirces availablo on thc World Wide
Web (WWW), subject-sorted into a total of 91 WWW Universal Resource Loca-
tor (URL) links in 16 categories. The book is iiitlexed and iridudcs an extensive
bibliography.

che cazzo è sta roba, postate della figa cristo

che cazzo è sta roba, postate della figa cristo

Scoperti ora?

va beh non tutti hanno 40 anni come te qui