Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information. In particular, for all n∈N , we assemble n×n squares using O(2log∗n) tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with O(2log∗K) tiles, where K denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct n×O(1) rectangles using only O(logn/loglogn) tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature. These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.
more »
« less
Early Elementary Students’ Use of Shape and Location Schemas When Embedding and Disembedding
Elementary students’ early development of embedding and disembedding is complex and paves the way for later STEM learning. The purpose of this study was to clarify the factors that support students’ embedding (i.e., overlapping shapes to form a new shape) and disembedding (i.e., identifying discrete shapes within another shape) through the use of filled shapes as opposed to shape frames. We recruited 26 Grade 1 students (~6–7 years old) and 23 Grade 3 students (~8–9 years old), asked them to work on two layered puzzle designs from the Color Code puzzle game, and interviewed them about their thinking processes. The first graders had higher success rates at fixing and embedding the tiles correctly, and students at both grade levels improved on the three-tile design when encountering it a second time about two months later. The four-tile design was more difficult, but students improved if they could identify a correct sub-structure of the design. Successful students used a combination of pictorial shape strategies and schematic location strategies, systematically testing tiles and checking how they could be embedded. The results suggest that helping students focus on sub-structures can promote their effective embedding.
more »
« less
- Award ID(s):
- 1759254
- NSF-PAR ID:
- 10371719
- Date Published:
- Journal Name:
- Education Sciences
- Volume:
- 12
- Issue:
- 2
- ISSN:
- 2227-7102
- Page Range / eLocation ID:
- 83
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Bortfeld, Heather ; de Haan, Michelle ; Nelson, Charles A. ; Quinn, Paul C. (Ed.)more » « less
Abstract Children's ability to discriminate nonsymbolic number (e.g., the number of items in a set) is a commonly studied predictor of later math skills. Number discrimination improves throughout development, but what drives this improvement is unclear. Competing theories suggest that it may be due to a sharpening numerical representation or an improved ability to pay attention to number and filter out non‐numerical information. We investigate this issue by studying change in children's performance (
N = 65) on a nonsymbolic number comparison task, where children decide which of two dot arrays has more dots, from the middle to the end of 1st grade (mean age at time 1 = 6.85 years old). In this task, visual properties of the dot arrays such as surface area are either congruent (the more numerous array has more surface area) or incongruent. Children rely more on executive functions during incongruent trials, so improvements in each congruency condition provide information about the underlying cognitive mechanisms. We found that accuracy rates increased similarly for both conditions, indicating a sharpening sense of numerical magnitude, not simply improved attention to the numerical task dimension. Symbolic number skills predicted change in congruent trials, but executive function did not predict change in either condition. No factor predicted change in math achievement. Together, these findings suggest that nonsymbolic number processing undergoes development related to existing symbolic number skills, development that appears not to be driving math gains during this period.Children's ability to discriminate nonsymbolic number improves throughout development. Competing theories suggest improvement due to sharpening magnitude representations or changes in attention and inhibition.
The current study investigates change in nonsymbolic number comparison performance during first grade and whether symbolic number skills, math skills, or executive function predict change.
Children's performance increased across visual control conditions (i.e., congruent or incongruent with number) suggesting an overall sharpening of number processing.
Symbolic number skills predicted change in nonsymbolic number comparison performance.
-
Inspired by nature and motivated by a lack of top-down tools for precise nanoscale manufacture, self-assembly is a bottom-up process where simple, unorganized components autonomously combine to form larger more complex structures. Such systems hide rich algorithmic properties - notably, Turing universality - and a self-assembly system can be seen as both the object to be manufactured as well as the machine controlling the manufacturing process. Thus, a benchmark problem in self-assembly is the unique assembly of shapes: to design a set of simple agents which, based on aggregation rules and random movement, self-assemble into a particular shape and nothing else. We use a popular model of self-assembly, the 2-handed or hierarchical tile assembly model, and allow the existence of repulsive forces, which is a well-studied variant. The technique utilizes a finely-tuned temperature (the minimum required affinity required for aggregation of separate complexes). We show that calibrating the temperature and the strength of the aggregation between the tiles, one can encode the shape to be assembled without increasing the number of distinct tile types. Precisely, we show one tile set for which the following holds: for any finite connected shape S, there exists a setting of binding strengths between tiles and a temperature under which the system uniquely assembles S at some scale factor. Our tile system only uses one repulsive glue type and the system is growth-only (it produces no unstable assemblies). The best previous unique shape assembly results in tile assembly models use O(K(S)/(log K(S))) distinct tile types, where K(S) is the Kolmogorov (descriptional) complexity of the shape S.more » « less
-
more » « less
Abstract In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form “flexible” bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either “genomes” specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be “deconstructed” by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.
-
Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External ForcesAdvances in technology have given us the ability to create and manipulate robots for numerous applications at the molecular scale. At this size, fabrication tool limitations motivate the use of simple robots. The individual control of these simple objects can be infeasible. We investigate a model of robot motion planning, based on global external signals, known as the tilt model. Given a board and initial placement of polyominoes, the board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked.We propose a new hierarchy of shapes and design a single configuration that is strongly universal for any w×h bounded shape within this hierarchy (it can be reconfigured to construct any w×h bounded shape in the hierarchy). This class of shapes constitutes the most general set of buildable shapes in the literature, with most previous work consisting of just the first-level of our hierarchy. We accompany this result with a O(n4logn)-time algorithm for deciding if a given hole-free shape is a member of the hierarchy. For our second result, we resolve a long-standing open problem within the field: We show that deciding if a given position may be covered by a tile for a given initial board configuration is PSPACE-complete, even when all movable pieces are 1×1 tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3390/educsci12020083
