Cellular Automata and Groups
Cellular automata were introduced in the first half of the last century by John von Neumann who used them as theoretical models for self-reproducing machines. The authors present a self-contained exposition of the theory of cellular automata on groups and
- PDF / 5,647,732 Bytes
- 446 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 247 Views
For further volumes: www.springer.com/series/3733
Tullio Ceccherini-Silberstein r Michel Coornaert
Cellular Automata and Groups
Tullio Ceccherini-Silberstein Dipartimento di Ingegneria Università del Sannio C.so Garibaldi 107 82100 Benevento Italy [email protected]
Michel Coornaert Institut de Recherche Mathématique Avancée Université de Strasbourg 7 rue René-Descartes 67084 Strasbourg Cedex France [email protected]
ISSN 1439-7382 e-ISBN 978-3-642-14034-1 ISBN 978-3-642-14033-4 DOI 10.1007/978-3-642-14034-1 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2010934641 Mathematics Subject Classification (2010): 37B15, 68Q80, 20F65, 43A07, 16S34, 20C07 © Springer-Verlag Berlin Heidelberg 2010 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: deblik Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
To Katiuscia, Giacomo, and Tommaso To Martine and Nathalie
Preface
Two seemingly unrelated mathematical notions, namely that of an amenable group and that of a cellular automaton, were both introduced by John von Neumann in the first half of the last century. Amenability, which originated from the study of the Banach-Tarski paradox, is a property of groups generalizing both commutativity and finiteness. Nowadays, it plays an important role in many areas of mathematics such as representation theory, harmonic analysis, ergodic theory, geometric group theory, probability theory, and dynamical systems. Von Neumann used cellular automata to serve as theoretical models for self-reproducing machines. About twenty years later, the famous cellular automaton associated with the Game of Life was invented by John Horton Conway and popularized by Martin Gardner. The theory of cellular automata flourished as one of the main branches of computer science. Deep connections with complexity theory and logic emerged from the discovery that some cellular automata are universal Turing machines. A group G is said to be amenable (as a discrete group) if the set of all subsets of G admits a right-invariant finitely additive probability measure. All finite groups, all solvable groups (and therefore all abelian groups), and all finitely generated grou
Data Loading...
