Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata

摘要

In this paper, we investigate how 1-D reversible cellular automata (RCAs) can simulate reversible Turing machines (RTMs) and cyclic tag systems (CTSs). A CTS is a universal string rewriting system proposed by M. Cook. First, we show that for any m-state n-symbol RTM there is a 1-D 2-neighbor RCA with a number of states less than (m + 2n + 1)(m + n + 1) that simulates it. It improves past results both in the number of states and in the neighborhood size. Second, we study the problem of finding a 1-D RCA with a small number of states that can simulate any CTS. So far, a 30-state RCA that can simulate any CTS and works on ultimately periodic infinite configurations has been given by K. Morita. Here, we show there is a 24-state 2-neighbor RCA with this property.