Thermodynamics and complexity of cellular automata

被引：22

作者：

Badii, R

Politi, A

机构：

[1] IST NAZL OTTICA,I-50125 FLORENCE,ITALY

[2] IST NAZL FIS NUCL,I-50125 FLORENCE,ITALY

来源：

PHYSICAL REVIEW LETTERS | 1997年 / 78卷 / 03期

关键词：

D O I：

10.1103/PhysRevLett.78.444

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

The complexity exhibited by cellular automata is studied using both topological (graph-theoretical) and metric (thermodynamic) techniques. A novel topological classification, based on a hierarchy of languages, is introduced. In particular, it is shown that the elementary rule 22 is able to produce, upon iteration, a deep nesting of grammatical rules and that this asymptotically yields a phase transition when the thermodynamic formalism is applied to the limit spatial configuration.

引用

收藏

页码：444 / 447

页数：4

相关论文

共 18 条

[1] TOPOLOGICAL ENTROPY [J].

ADLER, RL ;

KONHEIM, AG ;

MCANDREW, MH .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 114 (02) :309-&

[2]

ALEKSEEV VM, 1981, PHYS REP, V75, P287, DOI 10.1016/0370-1573(81)90186-1

[3] MEASUREMENT OF THE DIMENSION SPECTRUM F(ALPHA) - FIXED-MASS APPROACH [J].

BADII, R ;

BROGGI, G .

PHYSICS LETTERS A, 1988, 131 (06) :339-343

[4]

BADII R, 1985, J STAT PHYS, V40, P725, DOI 10.1007/BF01009897

[5] ON THE TOPOLOGY OF THE HENON MAP [J].

DALESSANDRO, G ;

GRASSBERGER, P ;

ISOLA, S ;

POLITI, A .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1990, 23 (22) :5285-5294

[6] HIERARCHICAL APPROACH TO COMPLEXITY WITH APPLICATIONS TO DYNAMIC-SYSTEMS [J].

DALESSANDRO, G ;

POLITI, A .

PHYSICAL REVIEW LETTERS, 1990, 64 (14) :1609-1612

[7]

Fahner G., 1987, Complex Systems, V1, P1093

[8] SCALING LAWS FOR INVARIANT-MEASURES ON HYPERBOLIC AND NONHYPERBOLIC ATTRACTORS [J].

GRASSBERGER, P ;

BADII, R ;

POLITI, A .

JOURNAL OF STATISTICAL PHYSICS, 1988, 51 (1-2) :135-178

[9] A HIERARCHICAL-CLASSIFICATION OF CELLULAR AUTOMATA [J].

GUTOWITZ, HA .

PHYSICA D, 1990, 45 (1-3) :136-156

[10]

Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation