Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2000
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/math/0003117 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913209540149248 |
|---|---|
| author | Gacs, Peter |
| author_facet | Gacs, Peter |
| contents | In a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information indefinitely is nontrivial, even in an infinite automaton. Still, there is a solution in 2 dimensions, and this solution can be used to construct a simple 3-dimensional discrete-time universal fault-tolerant cellular automaton. This technique does not help much to solve the following problems: remembering a bit of information in 1 dimension; computing in dimensions lower than 3; computing in any dimension with non-synchronized transitions.
Our more complex technique organizes the cells in blocks that perform a reliable simulation of a second (generalized) cellular automaton. The cells of the latter automaton are also organized in blocks, simulating even more reliably a third automaton, etc. Since all this (a possibly infinite hierarchy) is organized in ``software'', it must be under repair all the time from damage caused by errors. A large part of the problem is essentially self-stabilization recovering from a mess of arbitrary size and content. The present paper constructs an asynchronous one-dimensional fault-tolerant cellular automaton, with the further feature of ``self-organization''. The latter means that the initial configuration does not have to encode an infinite hierarchy -- this will be built up over time.
This is a corrected and strengthened version of the journal paper of 2001. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0003117 |
| institution | arXiv |
| publishDate | 2000 |
| record_format | arxiv |
| spellingShingle | Reliable Cellular Automata with Self-Organization Gacs, Peter Probability Distributed, Parallel, and Cluster Computing 60K35, 65Q80, 82C22, 37B15 In a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information indefinitely is nontrivial, even in an infinite automaton. Still, there is a solution in 2 dimensions, and this solution can be used to construct a simple 3-dimensional discrete-time universal fault-tolerant cellular automaton. This technique does not help much to solve the following problems: remembering a bit of information in 1 dimension; computing in dimensions lower than 3; computing in any dimension with non-synchronized transitions. Our more complex technique organizes the cells in blocks that perform a reliable simulation of a second (generalized) cellular automaton. The cells of the latter automaton are also organized in blocks, simulating even more reliably a third automaton, etc. Since all this (a possibly infinite hierarchy) is organized in ``software'', it must be under repair all the time from damage caused by errors. A large part of the problem is essentially self-stabilization recovering from a mess of arbitrary size and content. The present paper constructs an asynchronous one-dimensional fault-tolerant cellular automaton, with the further feature of ``self-organization''. The latter means that the initial configuration does not have to encode an infinite hierarchy -- this will be built up over time. This is a corrected and strengthened version of the journal paper of 2001. |
| title | Reliable Cellular Automata with Self-Organization |
| topic | Probability Distributed, Parallel, and Cluster Computing 60K35, 65Q80, 82C22, 37B15 |
| url | https://arxiv.org/abs/math/0003117 |