Reliable Cellular Automata with Self-Organization WD2NCBV9F0

URI	`m2://res/WD2NCBV9F0`
Kind	preprint
Creators	Peter Gacs
Date	2000-03-20
MSC	60-XX
Subjects	arxiv math.PR, arxiv cs.DC
Scope	in

Expressions

e1: version, preprint

Language	en
Date	2000-03-20
Ids	arXiv math/0003117, DOI 10.1023/a:1004823720305

Items in this resource

The mentions of the inventory that name this resource. Each name links to the card of its inventory row.

Item	Kind	Where	Source
Strong trajectory	definition	definition 7.10	arxiv
13KV6XA15H	statement	proposition 7.12	arxiv
Gap path	definition	definition 15.10	arxiv
181WY8606V	definition	definition 7.13	arxiv
1AG6RFZ5PW	example	example 5.14	arxiv
1BBSCQA1JV	example	example 14.15	arxiv
Encoding of finite sequences	definition	definition 5.9	arxiv
1HV5T1BDV1	statement	lemma 21.12	arxiv
Damage map	definition	definition 10.3	arxiv
1SJYRKJAWP	example	example 4.20	arxiv
Intrinsically universal cellular automata	definition	definition 4.22	arxiv
Encoding of infinite sequences	definition	definition 5.8	arxiv
Reliable computation in dim 1	statement	theorem 4	arxiv
Links	definition	definition 15.1	arxiv
Error-correcting code	definition	definition 5.13	arxiv
Indirectly given locations	definition	definition 9.17	arxiv
26WB6KK0K5	definition	definition 8.2	arxiv
28R6HJASV4	statement	lemma 20.7	arxiv
Events	definition	definition 2.11	arxiv
Variable-period cellular medium	definition	definition 4.14	arxiv
2J0E8GMVMF	example	example 7.20	arxiv
Effective age	definition	definition 8.5	arxiv
3AJDNS5DRJ	definition	definition 2.10	arxiv
3E58SQF5K6	statement	lemma 20.4	arxiv
3QC2DB0E5C	example	example 7.14	arxiv
Dwell period lower bound	definition	definition 7.18	arxiv
3TF0WZSK5T	definition	definition 5.4	arxiv
3WZ7G10ZXW	statement	lemma 21.5	arxiv
Reliable computation in finite or infinite space	statement	theorem 6	arxiv
Bad Gap Inference	statement	lemma 15.17	arxiv
4875XWCW3C	example	example 6.12	arxiv
Conditionals and various kinds of ``for''	definition	definition 9.8	arxiv
50M7BN9801	statement	lemma 21.10	arxiv
Commutative Simulation	statement	theorem 13	arxiv
Cell kinds	definition	definition 12.4	arxiv
5DE5KVT0TW	statement	lemma 21.7	arxiv
Color trickle-down	statement	lemma 21.8	arxiv
Interacting particle system	definition	definition 2.18	arxiv
5Q7JGY18T1	definition	definition 19.2	arxiv
Payload error checks	definition	definition 19.3	arxiv
Markov operator, invariance	definition	definition 6.3	arxiv
Locations for evaluation	definition	definition 9.18	arxiv
Deterministic cellular automata	definition	definition 2.4	arxiv
Non-adjacent neighbors	definition	definition 10.6	arxiv
6NNSG7Z860	definition	definition 21.1	arxiv
Random perturbation of a deterministic system	definition	definition 2.19	arxiv
6V44W2W6TY	statement	lemma 13.14	arxiv
72XHMQYFV1	definition	definition 14.3	arxiv
Space and states	definition	definition 2.2	arxiv
Remembering some bits	definition	definition 3.1	arxiv
Lattice configuration	definition	definition 4.12	arxiv
Info track	definition	definition 12.1	arxiv
Locations for the retrieval rule	definition	definition 9.15	arxiv
7E6F9A6WSJ	definition	definition 19.6	arxiv
Remembering a long string	statement	theorem 3	arxiv
General simulation	definition	definition 4.23	arxiv
Trickle-down	definition	definition 4.25	arxiv
Specification relation between strings	definition	definition 3.4	arxiv
Commutative transition	definition	definition 8.8	arxiv
8KDSMTMS3Z	definition	definition 10.8	arxiv
Colonies	definition	definition 12.3	arxiv
Local simulation	definition	definition 4.24	arxiv
Relaxation time	definition	definition 6.10	arxiv
A42TQAWJF8	definition	definition 6.13	arxiv
A65B1JTNAZ	definition	definition 15.2	arxiv
Running Gap	statement	corollary 15.13	arxiv
Special cases	example	example 10.17	arxiv
AR06ZBA5AQ	example	example 2.13	arxiv
ART1JGWCBE	statement	lemma 21.3	arxiv
Running Gap	statement	lemma 15.12	arxiv
AXN697ZBGT	statement	corollary 16.5	arxiv
Siblings	definition	definition 13.6	arxiv
B1S7F62YRR	statement	lemma 15.11	arxiv
Remembering a field in continuous time	statement	theorem 2	arxiv
Encoding	definition	definition 19.4	arxiv
Aggregated transition	example	example 4.21	arxiv
Adjacency	definition	definition 12.2	arxiv
Creation	statement	lemma 14.7	arxiv
Initially stable trickle-down amplifier	statement	lemma 5.12	arxiv
Invariant histories	definition	definition 8.6	arxiv
Present Attribution	statement	lemma 20.6	arxiv
BQEF960ZVT	definition	definition 11.1	arxiv
Location	definition	definition 9.11	arxiv
Code configuration	definition	definition 4.18	arxiv
C19801ZMKJ	definition	definition 8.9	arxiv
Trickle-down and initial stability for amplifiers	definition	definition 5.11	arxiv
C4JA2C1RRT	example	example 2.7	arxiv
Block code on configuration	definition	definition 4.16	arxiv
C7AR32M7RC	statement	theorem 14	arxiv
Amplifier	definition	definition 5.10	arxiv
Transition of a robust medium	definition	definition 10.7	arxiv
CG0KTWY946	definition	definition 5.5	arxiv
CKHD6DP5FW	example	example 13.2	arxiv
CY6E88BHTW	definition	definition 4.4	arxiv
CZ0Z37S0QV	definition	definition 2.1	arxiv
Fields	definition	definition 2.6	arxiv
D2W9K0114G	statement	lemma 21.11	arxiv
Simulation Damage Probability Bound	statement	lemma 10.5	arxiv
Colony Trace-back	statement	lemma 16.4	arxiv
Efficient universality	definition	definition 9.2	arxiv
Traceability	definition	definition 15.4	arxiv
G\'acs-Reif	statement	proposition 6.15	arxiv
Skirting	statement	lemma 15.5	arxiv
DYWCWGXV8M	example	example 5.16	arxiv
Overlap-free	definition	definition 4.15	arxiv
Local state subset functions	definition	definition 7.4	arxiv
Healing Cause	statement	lemma 15.14	arxiv
Controlling by a field	definition	definition 4.10	arxiv
EF23853XHK	definition	definition 9.3	arxiv
Stopping time	definition	definition 7.8	arxiv
Rules	definition	definition 9.6	arxiv
ESZR3CRZDR	definition	definition 12.10	arxiv
Color control	definition	definition 21.2	arxiv
The contact process.	example	example 22.1	arxiv
Weak convergence	definition	definition 6.2	arxiv
Dwell period	definition	definition 4.11	arxiv
Exposing	statement	lemma 14.17	arxiv
FSZ5ZCR6MT	statement	proposition 5.7	arxiv
Bad Gap Opening	statement	lemma 15.16	arxiv
FVDT2DNC19	example	example 5.15	arxiv
Depth	definition	definition 13.8	arxiv
Indicator function	definition	definition 8.4	arxiv
G2M6ADWS8B	definition	definition 9.19	arxiv
Basic Block Simulation	statement	theorem 16	arxiv
Special switching times	definition	definition 10.13	arxiv
Subset-function switching times	definition	definition 7.16	arxiv
GC0PJA5RTQ	definition	definition 6.1	arxiv
GC19F2XMA5	statement	theorem 8	arxiv
Standard alphabet	definition	definition 3.3	arxiv
Remembering a field in discrete time	statement	theorem 1	arxiv
GQENM8X0CK	example	example 4.8	arxiv
Legality	definition	definition 2.8	arxiv
Totally asynchronous cellular automata	definition	definition 8.1	arxiv
Hierarchical code	definition	definition 5.3	arxiv
Ergodicity	definition	definition 6.4	arxiv
Initial stability	definition	definition 4.26	arxiv
Marching soldiers	definition	definition 8.10	arxiv
H67XV71JNF	definition	definition 6.9	arxiv
Time consistency	definition	definition 13.5	arxiv
HB4HFV53VW	definition	definition 10.14	arxiv
Address	definition	definition 4.2	arxiv
Toom rule	definition	definition 6.6	arxiv
Domains	definition	definition 13.7	arxiv
HJZYWVE9MC	definition	definition 14.5	arxiv
HTAY8Z7F3Z	statement	lemma 20.5	arxiv
Creators, emergence	definition	definition 10.12	arxiv
J4K3Q4FY0Y	statement	lemma 15.8	arxiv
Name definitions	definition	definition 9.14	arxiv
J8FT733EWX	statement	lemma 14.6	arxiv
Combination of rules	definition	definition 9.7	arxiv
JNEPN11MZK	definition	definition 14.1	arxiv
JRFZVR2075	example	example 4.7	arxiv
Amplifier complex	definition	definition 11.2	arxiv
Variation distance	definition	definition 6.8	arxiv
Computation result	definition	definition 9.1	arxiv
KBM7T8X71X	example	example 7.3	arxiv
Trace-back path	definition	definition 15.6	arxiv
Glue	statement	lemma 14.19	arxiv
Successor	definition	definition 17.1	arxiv
KNBV20TVY2	definition	definition 14.4	arxiv
Filtration	definition	definition 2.12	arxiv
KT5FYKXG51	statement	theorem 7	arxiv
Update set	definition	definition 8.3	arxiv
KW24XZJEWF	example	example 9.10	arxiv
M0CYEF2B8Q	example	example 4.27	arxiv
M1QSV1SJ57	statement	proposition 4.17	arxiv
M5PMCR39P5	statement	lemma 20.3	arxiv
Capacity	definition	definition 2.5	arxiv
Composition of codes	definition	definition 5.1	arxiv
M9P0D87X1J	statement	proposition 7.6	arxiv
MCWMPGFTCH	statement	lemma 14.18	arxiv
MH35W82H21	statement	theorem 10	arxiv
MHTCN9QCT1	statement	lemma 6.11	arxiv
Carrying the payload	definition	definition 11.4	arxiv
Colony	definition	definition 4.1	arxiv
MSZAMQM4K1	statement	theorem 11	arxiv
Expansion and retrieval periods	definition	definition 12.7	arxiv
Fitted sequence	definition	definition 5.6	arxiv
Damage	definition	definition 10.2	arxiv
MZD8RT8Y8D	example	example 2.15	arxiv
N1T4D9VRJ4	definition	definition 21.6	arxiv
N2A8SE6026	statement	proposition 7.17	arxiv
Legality	statement	lemma 20.2	arxiv
Intrinsically universal cellular automata	statement	theorem 5	arxiv
Aggregating a field	definition	definition 4.9	arxiv
NC2E9FFGYB	statement	proposition 7.11	arxiv
Transition rate matrix	definition	definition 2.16	arxiv
Primitive variable-period medium	definition	definition 7.19	arxiv
Simulation by \( \CCA \	statement	theorem 9	arxiv
Random perturbation of a continous-time system	definition	definition 2.20	arxiv
Affecting	definition	definition 10.15	arxiv
Gaps	definition	definition 15.9	arxiv
The ``let'' construct	definition	definition 9.9	arxiv
Uniform program	definition	definition 11.5	arxiv
QCSMWCSAGV	statement	corollary 7.21	arxiv
Cover	statement	lemma 16.1	arxiv
QHPZHFG11Y	example	example 7.7	arxiv
QJPVGS180K	definition	definition 6.14	arxiv
Growth	statement	lemma 20.8	arxiv
QPSJMDD6D6	definition	definition 9.5	arxiv
QRR04HMD5F	definition	definition 13.9	arxiv
Healing field	definition	definition 14.12	arxiv
Locally maintained fields	definition	definition 13.1	arxiv
R5BFS8T52C	statement	lemma 21.9	arxiv
RH3TWSY6FB	definition	definition 3.5	arxiv
S680K5HEZV	example	example 7.1	arxiv
Attribution	definition	definition 16.2	arxiv
Self-organization	statement	lemma 21.14	arxiv
SDHWD95B7V	statement	proposition 5.17	arxiv
SE4608B14A	example	example 7.5	arxiv
Block simulation between deterministic cellular automata	definition	definition 4.19	arxiv
Age progress	definition	definition 15.7	arxiv
Crossing	statement	lemma 15.3	arxiv
Rule Language	statement	theorem 15	arxiv
Decoding	definition	definition 19.5	arxiv
Lasting color control	statement	lemma 21.4	arxiv
Boundary path	definition	definition 15.15	arxiv
Space-time	definition	definition 2.3	arxiv
TXJZCED9Y4	statement	lemma 19.7	arxiv
Amplifier	statement	lemma 11.7	arxiv
Multi-domain	definition	definition 13.13	arxiv
V6TTD5MXXM	statement	lemma 18.1	arxiv
Probabilistic color control	definition	definition 21.13	arxiv
VGGEV2APTJ	statement	lemma 20.1	arxiv
Attribution	statement	lemma 16.3	arxiv
VTNVR0VCJG	definition	definition 13.4	arxiv
VZ78YMY2JZ	definition	definition 12.8	arxiv
Probabilistic cellular automaton	definition	definition 2.14	arxiv
Deterministic cellular automaton with size parameters	definition	definition 4.13	arxiv
WDKMY0BMB2	example	example 5.2	arxiv
Healing	statement	lemma 17.2	arxiv
Injective canonical simulation	definition	definition 7.15	arxiv
Variable-period simulation	statement	corollary 8.11	arxiv
X01YKK8VSD	definition	definition 2.17	arxiv
Work period	definition	definition 4.3	arxiv
XH1WQWFEC7	statement	lemma 11.6	arxiv
Init	definition	definition 3.6	arxiv
Edges	definition	definition 13.11	arxiv
Constraint process	definition	definition 7.9	arxiv
Y1C4VDWRYM	definition	definition 8.7	arxiv
Endcells	definition	definition 14.9	arxiv
Errors	definition	definition 19.1	arxiv
Code on strings	definition	definition 4.5	arxiv
Trajectory	definition	definition 7.2	arxiv
Info location	definition	definition 9.12	arxiv
Z404GCM1NQ	definition	definition 2.9	arxiv
Z67H7XFBEC	statement	theorem 12	arxiv
ZNW0KMWCBX	statement	lemma 13.12	arxiv

Catalogue records

arxiv: math/0003117 (work)
arxiv_text: math/0003117 (work)