Difference between revisions of "Open Problems"

From self-assembly wiki
Jump to navigation Jump to search
Line 8: Line 8:
 
<li>In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[Fuzzy Temperature Fault Tolerance | fuzzy temperature model]] and showed that in this model n by n squares could efficiently self-assemble.  Can systems in this model also perform general computation?</li>
 
<li>In <ref name = SFTSAFT/>, Doty et al. introduced a model known as the [[Fuzzy Temperature Fault Tolerance | fuzzy temperature model]] and showed that in this model n by n squares could efficiently self-assemble.  Can systems in this model also perform general computation?</li>
  
<li>In [[Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue]], Patitz et al. introduced the ``restricted glue TAM'' (rgTAM), a version of the aTAM in which a single glue whose strength is -1 (i.e. it is repulsive) is allowed, and all other glues must be strength 1.  They showed that it is computationally universal.  However, is a 2HAM version of the rgTAM also computationally universal?</li>
+
<li>In [[Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue]], Patitz et al. introduced the ``restricted glue TAM`` (rgTAM), a version of the aTAM in which a single glue whose strength is -1 (i.e. it is repulsive) is allowed, and all other glues must be strength 1.  They showed that it is computationally universal.  However, is a 2HAM version of the rgTAM also computationally universal?</li>
  
 
<li>In <ref name = IUSA /> Doty et al. showed that the aTAM is [[Intrinsic universality of the aTAM | intrinsically universal]] for itself, but for [[Directed Tile Assembly Systems | directed]] systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems intrinsically universal for itself?</li>
 
<li>In <ref name = IUSA /> Doty et al. showed that the aTAM is [[Intrinsic universality of the aTAM | intrinsically universal]] for itself, but for [[Directed Tile Assembly Systems | directed]] systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems intrinsically universal for itself?</li>
Line 23: Line 23:
  
 
<li>In [[Computability and Complexity in Self-Assembly]], it was shown that for every computably enumerable language $L \subset \mathbb{N}$, a pattern representing $L$ [[Weak_Self-Assembly | weakly self-assembles]] along the x-axis, but with the points spread out roughly quadratically.  Can those points instead be spread out by only a constant factor? (Or with no space between them as with decidable languages as shown in [[Self-Assembly of Decidable Sets]]?)</li>
 
<li>In [[Computability and Complexity in Self-Assembly]], it was shown that for every computably enumerable language $L \subset \mathbb{N}$, a pattern representing $L$ [[Weak_Self-Assembly | weakly self-assembles]] along the x-axis, but with the points spread out roughly quadratically.  Can those points instead be spread out by only a constant factor? (Or with no space between them as with decidable languages as shown in [[Self-Assembly of Decidable Sets]]?)</li>
 +
 +
<li>In [[One_Tile_to_Rule_Them_All:_Simulating_Any_Turing_Machine,_Tile_Assembly_System,_or_Tiling_System_with_a_Single_Puzzle_Piece]], Demaine et al. showed that it is possible to turn any aTAM system into a single rotatable (non-square) tile which simulates it.  They also showed how to adapt this result to convert any of a variety of plane tiling systems (such as Wang tiles) into a "nearly" plane tiling system with a single tile (but with small gaps between the tiles).  An open question is whether or not this can be improved to result in a system which fully tiles the plane. (This has been an open problem in tiling theory for many years.)</li>
  
 
==References==
 
==References==

Revision as of 12:36, 13 June 2015

The following is a partial list of some of the many open problems in self-assembly: