Universal logic elements constructed on the Turing Tumble
- PDF / 943,365 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 127 Downloads / 368 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Universal logic elements constructed on the Turing Tumble Takahiro Tomita1 Naotake Kamiura1
•
Jia Lee2 • Teijiro Isokawa1 • Ferdinand Peper3 • Takayuki Yumoto1
•
Ó Springer Nature B.V. 2019
Abstract This paper presents a mathematical model for a mechanical computer called the Turing Tumble. We show that our model called Turing Tumble Model (TTM) is computationally universal under the assumptions that a configuration of TTM is sufficiently large and that local interactions between elements can be transferred without limitations. The Turing Tumble has a strict constraint, based on gravity, since signals can only move from top to bottom. We introduce a uniform scheme that takes into account this restriction in directionality to construct universal machines in the TTM based on directed acyclic graphs. This model may be useful for implementing computers that exploit mechanical interactions in nature, especially those on micrometer-scales. Keywords Mechanical computer Sequential machine Computational universality
1 Introduction Computation on micrometer-sized devices will be important for constructing molecular robots (Murata et al. 2013), in which chemical reactions or mechanical interactions between biomolecules and DNA molecules are used for operations. Several constructions for such computing systems have been proposed, such as molecular switch elements (Rondelez 2012) and Gellular Automata (Hagiya et al. 2014). Their operations are based on chemical reactions, which is efficient for energy consumption, though their reaction speeds tend to be low.
A short version of this paper was presented at AUTOMATA2018 (Tomita et al. 2018). & Takahiro Tomita [email protected] Teijiro Isokawa [email protected] 1
Graduate School of Engineering, University of Hyogo, Himeji, Hyogo, Japan
2
College of Computer Science, Chongqing University, Chongqing, China
3
Center for Information and Neural Networks, National Institute of Information and Communications Technology, and Osaka University, Osaka, Japan
Utilizing mechanical properties of micro-scaled structures will be an alternative candidate for molecular-sized devices, and there have been many mechanical implementations based on so-called Micro Electro Mechanical Systems (MEMS) technologies. Recently, a game called Turing Tumble has been released on the market (Turing Tumble—build marblepowered computers. https://www.turingtumble.com/) for educational purposes to aid the understanding of the mechanisms underlying computation. This game consists of various mechanical components that are configured on a two-dimensional board, as well as balls that are used as signals to drive these components. A ball injected from the top of the board flows along the configuration, while being operated on by the components. The potential energy in a ball is consumed through the computation process in this game, thus allowing gravitation-driven computation to be conducted. The creator of this computer has mentioned that it is Turing-c
Data Loading...
