Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1995 | Buch

Turing Computability and Complexity Kapitel lesen Erstes Kapitel lesen

Models of Massive Parallelism

Analysis of Cellular Automata and Neural Networks

verfasst von: Prof. Dr. Max Garzon

Verlag: Springer Berlin Heidelberg

Buchreihe : Texts in Theoretical Computer Science. An EATCS Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Locality is a fundamental restriction in nature. On the other hand, adaptive complex systems, life in particular, exhibit a sense of permanence and time­ lessness amidst relentless constant changes in surrounding environments that make the global properties of the physical world the most important problems in understanding their nature and structure. Thus, much of the differential and integral Calculus deals with the problem of passing from local information (as expressed, for example, by a differential equation, or the contour of a region) to global features of a system's behavior (an equation of growth, or an area). Fundamental laws in the exact sciences seek to express the observable global behavior of physical objects through equations about local interaction of their components, on the assumption that the continuum is the most accurate model of physical reality. Paradoxically, much of modern physics calls for a fundamen­ tal discrete component in our understanding of the physical world. Useful computational models must be eventually constructed in hardware, and as such can only be based on local interaction of simple processing elements.

Inhaltsverzeichnis

Frontmatter
1. Turing Computability and Complexity
Abstract
Ancient documents, like the Rhind Papyrus, dating as far back as 3600 B.C. attest to the fact that men have been performing computations for thousands of years, and for very practical reasons such as farming, land measurements (Egyptian geometry), or simply wishful thinking about the powers of human prediction (astrology). Years later, after Europe surmounted the laggish period of the Middle Ages, a reblooming in the arts during the Renaissance slowly led the way to the dawn of the scientific method, specifically, in the physical- mathematical sciences, with Galileo and the crowning work of Newton on celestial mechanics. In particular, from a modern perspective, their monumental work provides us with algorithms to establish facts about heavenly or earthly objects related to their position and/or their motion. Further research on electricity and magnetism by J.C. Maxwell, and on thermodynamics and heat theory by L. Boltzmann and other 19th century physicists may be regarded in a similar way.
Max Garzon
2. Cellular Automata
Abstract
In this chapter we define the fundamental concepts and establish our notation. One of the problems in surveying the literature of cellular automata is the great variety of notation and terminology that has been developed over the years by various authors to describe similar concepts and results. As a consequence, many results have been (and continue to be) rediscovered a number of times in a number of guises. Although the definitions, concepts, and notations given in this chapter may not be, in few instances, the most common current use, they at least provide a consistent framework to deal with general types of cellular automata. Moreover, this notational framework can be easily extended to include neural and other types of networks.
Max Garzon
3. Linear Cellular Automata
Abstract
In the theory of classical systems, linear concepts play a fundamental role for at least two reasons: (a) they are usually about the only ones that admit a satisfactory mathematical analysis; and (b) nonlinear systems can usually be studied through linear approximations. At least part (a) has been true in the study of cellular automata. Emerging evidence suggests that (b) may bear some truth as well. In this chapter we introduce linear cellular automata and study their basic properties. We assume, as usual, that the nodes in the center cell‘s neighborhood N have been numbered in a fixed (but arbitrary) order x 1… x 2… x n and that N . denotes N expanded to include the center cell.
Max Garzon
4. Semi-totalistic Automata
Abstract
In view of how tractable linear rules turn out to be, one is encouraged to investigate similar questions for more general rules. A natural next step is to make the next state of a center cell depend, not linearly on the full local distribution of neighboring cells, but rather on the their density and, possibly, its own state. For instance, under a majority rule for an elementary celullar automaton the center cell polls its neighbors for a state and goes with the majority (ties are broken arbitrarily by the center cell, for instance by keeping its current state). These rules are called semi-totalistic. In the particular case of elementary automata, it is necessary to reduce this total count to a binary value. The simplest way to achieve this reduction is to set up a minimal threshold value for the count to become 1.
Max Garzon
5. Decision Problems
Abstract
One of the puzzling aspects about local rules of cellular automata is that despite their behavioral complexity, they are describable by finite tables that require only finitely many symbols and can be fed as input to a conventional computer. It is therefore natural to ask whether one could, at least in principle, write a program for a von Neumann computer that would answer questions, as some sort of pre-processing or short-cut, about the effect in the large of local rule inputs. For instance one may ask, is the global effect of the input local rule injective? Is it surjective? If reversible, what is the inverse that will undo the change caused by the rule? And so forth.
Max Garzon
6. Neural and Random Boolean Networks
Abstract
One of the fundamental features of cellular automata is the homogeneity of the underlying cellular space. It is natural to ask whether this is a fundamental restriction or just a convenient assumption. In order to gain some insight into this question, it is necessary to relax our restriction on the homogeneity of the space and allow more general interconnections between the sites of the space. This chapter discusses the nature of the resulting generalizations and compares the power of the resulting models vis-a-vis Turing machines and cellular automata.
Max Garzon
7. General Properties
Abstract
Perhaps the most fundamental problem in the study of cellular automata concerns the classification of local rules according to a natural notion of equivalence related to their long-time behavior. One of the difficulties in answering this question is precisely the fact that there is not a single most dominant aspect in the long-term evolution of a global map. Previous chapters have dealt with particular types of local rules and their properties. Even totalistic rules of the type considered in Chapter 4 show that a bottom-up approach to the classification of cellular automaton dynamics in terms of our ability to predict their long-term behavior is not fine enough to constitute a satisfactory categorization.
Max Garzon
8. Classification
Abstract
Cellular automata and discrete neural networks constitute very simple and general models that seem to capture the fundamental features of a variety of highly complex systems. Their study offers the possibility of obtaining some understanding of the most important and characteristic properties of complex and self-organizing systems, the evolution of which currently appears chaotic, disorganized and beyond the scope of known laws of nature.
Max Garzon
9. Asymptotic Behavior
The difficulties in classifying cellular automata and networks based on their global behavior have been explained in Chapter 8. The results tend to indicate that a complete classification is, at least in many computational ways, impractical or unfeasible. The study of the specific properties of global behavior of arbitrary automata in terms of their local rules is indeed a most interesting and difficult problem.
Among other reasons for this difficulty is that these problems appear to be of a discrete and combinatorial nature, where classical optimization and analysis are not directly applicable. This chapter deals with positive results that shed light on the long-term behavior of global dynamics. Each technique has only been partially successful and they can be roughly classified as either discrete/combinatorial or analytic. The first section presents some results obtained through combinatorial techniques. Later, several analogies with continuous classical dynamical systems are exploited to gain insight into the nature of the long-term behavior of cellular networks. Despite complex behavior as chaotic as that of maps on the interval, many of them exhibit an interesting property of observability through simulation on computing devices under limitations such as bounded precision, rounding errors, and noise.
Max Garzon
10. Some Inverse Problems
Abstract
As explained in Chapter 2, conventional computing requires encoding of information into strings of symbols over a given alphabet. Classical computation thus deals with recognition and generation problems of formal languages consisting of words (strings of symbols). Classical computational theories originated in attempts to understand calculation as performed by humans. All the resultant models (Turing machines, Church’s A-calculus, Chomsky grammars, Markov algorithms, etc.) are based on the seemingly sequential nature of conscioushuman calculation. They are inherently sequential.
Old folk
11. Real Computation
Abstract
Like formal language recognition, computation of real-valued functions is a well- defined area of classical computation. The concept was the motivation behind the celebrated Turing paper on computable numbers and has been studied ever since. Given the fact that sequential computing devices (Turing machines and the like) are countable in number and process information coded as finite strings of symbols over a bounded alphabet, the various notions of computable function are necessarily of an approximative nature. Now, generalizations of computabil- ity have been made on various types of assumptions.
Charles P. Baudelaire
12. A Bibliography of Applications
Abstract
Although this volume has been chielfy concerned with analysis of various aspects of the evolution of cellular automata and generalizations, their applications have played a catalytic role in their genesis and study. A survey would not be fairly complete without a description, even if superficial, of the major applications of cellular models (including probabilistic cellular automata).
The Wolfram collection [Wo5, Sects. 6–9] contains an annotated bibliography of applications in various fields up to its publication (1986), to which the reader is referred. Most of the sections below cite later references.
Max Garzon
Backmatter
Metadaten
Titel
Models of Massive Parallelism
verfasst von
Prof. Dr. Max Garzon
Copyright-Jahr
1995
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-77905-3
Print ISBN
978-3-642-77907-7
DOI
https://doi.org/10.1007/978-3-642-77905-3