Show simple item record

dc.contributor.authorGacs, Peteren_US
dc.date.accessioned2011-10-20T05:06:43Z
dc.date.available2011-10-20T05:06:43Z
dc.date.issued1998-01-05en_US
dc.identifier.citationGacs, Peter. "Reliable Cellular Automata with Self-Organization", Technical Report BUCS-1998-002, Computer Science Department, Boston University, January 15, 1998. [Available from: http://hdl.handle.net/2144/1759]en_US
dc.identifier.urihttps://hdl.handle.net/2144/1759
dc.description.abstractIn a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information for more than a constant number of steps 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 caused by the faults. 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 to be periodical with a small period.en_US
dc.description.sponsorshipNational Science Foundation (CCR-920484)en_US
dc.language.isoen_USen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1998-002en_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.titleReliable Cellular Automata with Self-Organizationen_US
dc.typeTechnical Reporten_US


Files in this item

This item appears in the following Collection(s)

Show simple item record