Show simple item record

dc.contributor.authorGacs, Peteren_US
dc.date.accessioned2018-06-14T19:48:38Z
dc.date.available2018-06-14T19:48:38Z
dc.date.issued2001-04-01
dc.identifierhttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000168235400002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=6e74115fe3da270499c3d65c9b17d654
dc.identifier.citationP Gacs. 2001. "Reliable cellular automata with self-organization." Journal of Statistical Physics, Volume 103, Issue 1-2, pp. 45 - 267 (223).
dc.identifier.issn0022-4715
dc.identifier.issn1572-9613
dc.identifier.urihttps://hdl.handle.net/2144/29390
dc.description.abstractIn 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 unless a large amount of input information must be given, the initial configuration can be chosen homogeneous.en_US
dc.format.extentp. 45 - 267en_US
dc.languageEnglish
dc.publisherSPRINGERen_US
dc.relation.ispartofJOURNAL OF STATISTICAL PHYSICS
dc.subjectScience & technologyen_US
dc.subjectPhysical sciencesen_US
dc.subjectPhysics, mathematicalen_US
dc.subjectPhysicsen_US
dc.subjectProbabilistic cellular automataen_US
dc.subjectInteracting particle systemsen_US
dc.subjectRenormalizationen_US
dc.subjectErgodicityen_US
dc.subjectReliabilityen_US
dc.subjectFault-toleranceen_US
dc.subjectError-correctionen_US
dc.subjectSimulationen_US
dc.subjectHierarchyen_US
dc.subjectSelf-organizationen_US
dc.subjectInteracting particle systemsen_US
dc.subjectMathematical sciencesen_US
dc.subjectFluids & plasmasen_US
dc.titleReliable cellular automata with self-organizationen_US
dc.typeArticleen_US
dc.identifier.doi10.1023/A:1004823720305
pubs.elements-sourceweb-of-scienceen_US
pubs.notesEmbargo: No embargoen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US


This item appears in the following Collection(s)

Show simple item record