Difference between revisions of "Building n by n squares"
Jhendricks (talk | contribs) (Created page with "__TOC__ ==Building $n \times n$ squares== Since Winfree showed in his thesis \cite{Winf98} that the aTAM is computationally universal, we know that we can algorithmically direct ...") |
Jhendricks (talk | contribs) (→Building $n \times n$ squares) |
||
| Line 1: | Line 1: | ||
__TOC__ | __TOC__ | ||
==Building $n \times n$ squares== | ==Building $n \times n$ squares== | ||
| − | Since Winfree showed in his thesis \cite{Winf98} that the aTAM is computationally universal, we know that we can algorithmically direct the growth of assemblies. This ability allows for not only the creation of complicated and precise shapes, but also often for them to be created very tile type efficiently (i.e. they require small tile sets - those with few numbers of unique tile types). A benchmark problem for tile-based self-assembly is that of assembling an $n \times n$ square since this requires that the tiles somehow compute the value of $n$ and thus | + | Since Winfree showed in his thesis \cite{Winf98} that the aTAM is computationally universal, we know that we can algorithmically direct the growth of assemblies. This ability allows for not only the creation of complicated and precise shapes, but also often for them to be created very tile type efficiently (i.e. they require small tile sets - those with few numbers of unique tile types). A benchmark problem for tile-based self-assembly is that of assembling an $n \times n$ square since this requires that the tiles somehow compute the value of $n$ and thus "know when to stop" at the boundaries. In \cite{RotWin00} Rothemund and Winfree showed that binary counters can be used to guide the growth of squares and that thereby it is possible to self-assemble an $n \times n$ square using $O(\log n)$ tile types. |
Revision as of 11:31, 11 June 2013
Contents
Building \(n \times n\) squares
Since Winfree showed in his thesis \cite{Winf98} that the aTAM is computationally universal, we know that we can algorithmically direct the growth of assemblies. This ability allows for not only the creation of complicated and precise shapes, but also often for them to be created very tile type efficiently (i.e. they require small tile sets - those with few numbers of unique tile types). A benchmark problem for tile-based self-assembly is that of assembling an \(n \times n\) square since this requires that the tiles somehow compute the value of \(n\) and thus "know when to stop" at the boundaries. In \cite{RotWin00} Rothemund and Winfree showed that binary counters can be used to guide the growth of squares and that thereby it is possible to self-assemble an \(n \times n\) square using \(O(\log n)\) tile types.
