Abstract

In this note we consider register-machines with symbol manipulation capabilities. They can form words over a given alphabet in their registers by appending symbols to the strings already stored. These machines are similar to Post's normal systems and the related machine-models discussed in the literature. But unlike the latter devices they are deterministic and are not allowed to read symbols from the front of the registers. Instead they can compare registers and erase them. At first glance it is surprising that in general these devices are as powerful as the seemingly stronger models. Here we investigate the borderline of universality for these machines