Cellular Automata and Discrete Complex Systems

Name: Cellular Automata and Discrete Complex Systems | 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings

Matthew Cook Turlough Neary(Herausgeber*in)

Springer (Verlag)

Erschienen am 1. Juni 2016

XVI, 199 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-39300-1 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Invited Talk Abstracts
Automata, Semigroups and Dynamical Systems
Propagation, Diffusion and Randomization in Cellular Automata
What Automata Can Provide a Medium for Life?
A Brief Tour of Theoretical Tile Self-Assembly
Contents
Invited Papers
Propagation, Diffusion and Randomization in Cellular Automata
1 Introduction
2 Formal Definitions
2.1 Diamonds and Their Dynamics
2.2 Ergodic Dynamics
3 The Ideal World of 1D Abelian Linear Cellular Automata
3.1 A Characterization of Randomizing CA
3.2 Interesting Reversible Examples
References
What Automata Can Provide a Medium for Life?
1 Introduction
2 Some Historical Notes
3 Methodological Problems
3.1 von Neumann's Fixed-Point Trick
3.2 Computation Universality Is Not Enough
3.3 The Fragility of ``All Mine!''
4 Specific Ergodicity
5 Emergence
6 Life and Evolution
7 Conclusions
References
A Brief Tour of Theoretical Tile Self-Assembly
References
Regular Papers
The Corona Limit of Penrose Tilings Is a Regular Decagon
1 Introduction
2 Corona Limit
3 Penrose Tilings
4 Growth Cellular Automaton on Penrose Tilings
5 Rhombus von Neumann Neighborhood Case
6 The Difference of Growth Speeds
7 Conclusion
References
The Group of Reversible Turing Machines
1 Introduction
1.1 Turing Machines and Their Generalization
1.2 Our Results and Comparisons with Other Groups
1.3 Preliminaries
2 Two Models for Turing Machine Groups
2.1 The Moving Head Model
2.2 The Moving Tape Model
2.3 The Uniform Measure and Reversibility
2.4 Classical Turing Machines
3 Properties of RTM and Interesting Subgroups
3.1 Local Permutations and Oblivious Turing Machines
3.2 Finite-State Automata
3.3 Elementary Turing Machines and the LEF Property of RTM
4 Computability Aspects
4.1 Basic Decidability Results
4.2 The Torsion Problem
References
Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata
1 Introduction
2 Definitions and Properties
3 Dynamics, Simulation and Normalization
4 Formal Discretization
5 Correctness
6 Conclusion
References
An ``almost dual'' to Gottschalk's Conjecture
1 Introduction
2 Background
3 Post-surjectivity
4 Post-surjectivity on Sofic Groups
5 Conclusions
References
On Finite Monoids of Cellular Automata
1 Introduction
2 Basic Results
3 The Structure of ICA(G
A)
4 Generating Sets of of CA(G
A)
References
Sum of Exit Times in Series of Metastable States in Probabilistic Cellular Automata
1 Introduction
2 The Model
3 Metastable States and Main Results
3.1 Potential Theoretic Approach and Capacities
3.2 Series of Metastable States for PCA Without Self-interaction
4 Sketch of proof of Theorem3.1
4.1 Proof of Lemma3.5
References
Partial Reversibility of One-Dimensional Cellular Automata
1 Introduction
2 Background
2.1 Basics
2.2 Partial Reversibility Classes
3 Reversibility Degree
3.1 Reappraisal of Relative Partial Reversibility in
3.2 Absolute Partial Reversibility
3.3 Partial Reversibility Degree of Individual Elementary Rules
4 Concluding Remarks
References
Two-Dimensional Traffic Rules and the Density Classification Problem
1 Introduction
2 Basics
2.1 Setting
2.2 Presentation of the Problem
2.3 Known Results with Cellular Automata
3 Particle Systems Solutions to the Spacing Problem
3.1 Our Model of IPS
3.2 No Solution to the Strict Spacing Problem
3.3 An IPS that Synchronises Checkerboards
3.4 Glauber Dynamics
4 The Density Classification Problem on Finite Lattices
5 Some Questions
References
Constant Acceleration Theorem for Extended von Neumann Neighbourhoods
1 Definitions
1.1 Cellular Automata
1.2 Picture Recognition
2 Main Result
References
Shrinking and Expanding Cellular Automata
1 Introduction
2 Basics
2.1 Standard CA
2.2 Shrinking and Expanding CA
3 Relating ATM Time to SXCA Time
4 Relating SXCA Time to TM Space
5 Conclusion and Outlook
References
An 8-State Simple Reversible Triangular Cellular Automaton that Exhibits Complex Behavior
1 Introduction
2 Elementary Triangular Partitioned Cellular Automata
3 RETPCA T0347 and Its Properties
3.1 Glider, Block, Fin, and Rotator in T0347
3.2 Changing the Move Direction of a Glider by Blocks
3.3 Glider Guns in T0347
4 T0347 is Computationally Universal
4.1 Showing Turing Universality of Reversible CA
4.2 Making Switch Gate and Inverse Switch Gate Modules in T0347
5 Concluding Remarks
References
Cellular Automata on Group Sets and the Uniform Curtis-Hedlund-Lyndon Theorem
1 Left Group Actions
2 Right Quotient Set Semi-Actions
3 Semi-Cellular and Cellular Automata
4 Invariance, Equivariance, Determination, and Composition of Global Transition Functions
5 Curtis-Hedlund-Lyndon Theorems
6 Invertibility
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken