Algebra Seminar
Speaker: Lila Kari (Western)
"The undecidability of the infinite ribbon problem: implications for computing by self-assembly"
Time: 15:30
Room: MC 106
Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world and has recently become of interest due to advances in nanotechnology. A systematic study of self-assembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The components are modelled as
square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a ``glue'', and two adjacent tiles stick iff they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional structures or may cover the entire plane. We prove that it is undecidable whether an arbitrary finite set of tiles can be used to assemble an infinite ribbon. While the problem can be shown undecidable by existing techniques if the ribbon must start with a given ``seed'' tile, our result settles the ``unseeded'' case, an open problem known as the ``unlimited infinite snake problem''.
Mathematics Calendar 
Week of April 12, 2009
