Crossing information in two-dimensional Sandpiles

Author	dc.contributor.author	Gajardo, A.
Author	dc.contributor.author	Goles Chacc, Eric, 1951-	es_CL
Admission date	dc.date.accessioned	2009-04-07T10:01:00Z
Available date	dc.date.available	2009-04-07T10:01:00Z
Publication date	dc.date.issued	2006-12-15
Cita de ítem	dc.identifier.citation	THEORETICAL COMPUTER SCIENCE Volume: 369 Issue: 1-3 Pages: 463-469 Published: DEC 15 2006	en
Identifier	dc.identifier.issn	0304-3975
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/124869
Abstract	dc.description.abstract	We prove that in a two-dimensional Sandpile automaton, embedded in a regular infinite planar cellular space, it is impossible to cross information, if the bit of information is the presence (or absence) of an avalanche. This proves that it is impossible to embed arbitrary logical circuits in a Sandpile through quiescent configurations. Our result applies also for the non-planar neighborhood of Moore. Nevertheless, we also show that it is possible to compute logical circuits with a two-dimensional Sandpile, if a neighborhood of radius two is used in Z(2); crossing information becomes possible in that case, and we conclude that for this neighborhood the Sandpde is P-complete and Turing universal.	en
Lenguage	dc.language.iso	en	en
Publisher	dc.publisher	ELSEVIER	en
Keywords	dc.subject	Sandpile	en
Título	dc.title	Crossing information in two-dimensional Sandpiles	en
Document type	dc.type	Artículo de revista