MURAL - Maynooth University Research Archive Library



    Turning machines: a simple algorithmic model for molecular robotics


    Kostitsyna, Irina, Wood, Cai and Woods, Damien (2024) Turning machines: a simple algorithmic model for molecular robotics. Natural Computing, 23 (2). pp. 407-430. ISSN 1572-9796

    [thumbnail of s11047-022-09880-8.pdf]
    Preview
    Text
    s11047-022-09880-8.pdf
    Available under License Creative Commons Attribution Non-commercial Share Alike.

    Download (6MB) | Preview

    Abstract

    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 provide a suite of tools for reasoning about Turning Machines by fully characterising their ability to execute line rotations: executing an almost-full line rotation of $$5\pi /3$$ 5 π / 3 radians is possible, yet a full $$2\pi$$ 2 π rotation is impossible. Furthermore, line rotations up to $$5\pi /3$$ 5 π / 3 are executed efficiently, in $$O(\log n)$$ O ( log n ) expected time in our continuous time Markov chain time model. We then show that such line-rotations represent a fundamental primitive in the model, by using them to efficiently and asynchronously fold shapes. In particular, arbitrarily large zig-zag-rastered squares and zig-zag paths are foldable, as are y -monotone shapes albeit with error (bounded by perimeter length). Finally, we give shapes that despite having paths that traverse all their points, are in fact impossible to fold, as well as techniques for folding certain classes of (scaled) shapes without error. Our approach relies on careful geometric-based analyses of the feats possible and impossible by a very simple robotic system, and pushes conceptional hardness towards mathematical analysis and away from molecular implementation.
    Item Type: Article
    Keywords: Model of computation; Algorithmic molecular robotics; Self-assembly; Nubot; Reconfiguration;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 19694
    Identification Number: 10.1007/s11047-022-09880-8
    Depositing User: Damien Woods
    Date Deposited: 14 Apr 2025 14:51
    Journal or Publication Title: Natural Computing
    Publisher: Springer
    Refereed: Yes
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/19694
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads