A general architecture of oritatami systems for simulating arbitrary finite automata

04/23/2019

∙

by   Yo-Sub Han, et al.

∙

0

∙

share

In this paper, we propose an architecture of oritatami systems with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and O(t^4 ^2 t) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 329 bead types and requires just O(t |Q|^4 |Σ|^2) steps to simulate an NFA over an input alphabet Σ with a state set Q working on a word of length t.