Universal Reversible Turing Machines with a Small Number of Tape Symbols

We study the problem of finding small universal reversible Turing machines (URTMs) with four symbols or less. Here, we present two models of URTMs: a 24-state 4-symbol URTM, and a 32-state 3-symbol URTM. Both of them are designed so that they can simulate cyclic tag systems, a kind of string rewriting systems that are universal. By converting the 24-state 4-symbol URTM into a 2-symbol machine, we also obtain a 138-state 2-symbol URTM.