Search Results

Documents authored by Wood, Cai

Turning Machines

Authors: Irina Kostitsyna, Cai Wood, and Damien Woods

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Molecular robotics is challenging, so it seems best to keep it simple. We consider an abstract molecular robotics model based on simple folding instructions that execute asynchronously. Turning Machines are a simple 1D to 2D folding model, also easily generalisable to 2D to 3D folding. A Turning Machine starts out as a line of connected monomers in the discrete plane, each with an associated turning number. A monomer turns relative to its neighbours, executing a unit-distance translation that drags other monomers along with it, and through collective motion the initial set of monomers eventually folds into a programmed shape. We fully characterise the ability of Turning Machines to execute line rotations, and to do so efficiently: computing an almost-full line rotation of 5π/3 radians is possible, yet a full 2π rotation is impossible. We show that such line-rotations represent a fundamental primitive in the model, by using them to efficiently and asynchronously fold arbitrarily large zig-zag-rastered squares and y-monotone shapes.

Cite as

Irina Kostitsyna, Cai Wood, and Damien Woods. Turning Machines. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

  author =	{Kostitsyna, Irina and Wood, Cai and Woods, Damien},
  title =	{{Turning Machines}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-129649},
  doi =		{10.4230/LIPIcs.DNA.2020.11},
  annote =	{Keywords: model of computation, molecular robotics, self-assembly, nubot, reconfiguration}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail