Descripción



Selfassembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. Recent experiments in selfassembly demonstrate its potential for the parallel creation of a large number of nanostructures, including possibly computers. A systematic study of selfassembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The individual components are modeled as square tiles on the infinite twodimensional plane. Each side of a tile is covered by a specific ¿glue,¿ and two adjacent tiles will stick iff they have matching glues on their abutting edges. Tiles that stick to each other may form various twodimensional ¿structures¿ such as squares and rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called a ribbon: a nonselfcrossing rectilinear sequence of tiles on the plane, in which successive tiles are adjacent along an edge and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. While the problem can be proved undecidable using existing techniques if the ribbon is required to start with a given ¿seed¿ tile, our result settles the ¿unseeded¿ case, an open problem formerly known as the ¿unlimited infinite snake problem.¿ The proof is based on a construction, due to R. Robinson, of a special set of tiles that allow only aperiodic tilings of the plane. This construction is used to create a special set of directed tiles (tiles with arrows painted on the top) with the ¿strong planefilling property¿¿a variation of the ¿planefilling property¿ previously defined by J. Kari. A construction of ¿sandwich¿ tiles is then used in conjunction with this special tile set, to reduce the wellknown undecidable tiling problem to the problem of the existence of an infinite directed zipper (a special kind of ribbon). A ¿motif¿ construction is then introduced that allows one tile system to simulate another by using geometry to represent glues. Using motifs, the infinite directed zipper problem is reduced to the infinite ribbon problem, proving the latter undecidable. An immediate consequence of our result is the undecidability of the existence of arbitrarily large structures selfassembled using tiles from a given tile set.  
Internacional

Si 
JCR del ISI

Si 
Título de la revista

SIAM JOURNAL ON COMPUTING 
ISSN

00975397 
Factor de impacto JCR

1,459 
Información de impacto


Volumen

38 
DOI

http://dx.doi.org/10.1137/080723971 
Número de revista

6 
Desde la página

2356 
Hasta la página

2381 
Mes

MARZO 
Ranking
