Automatic Register Machine: A Computation Model with Automatic Functions and Relations as its Operations
ABSTRACT:
We propose a new model of computation incorporating automatic functions and relations as primitive operations, called Automatic Register Machine. We show that the model is able to generalize register machine operations without giving an unrealistic speed up, thus it is comparable to fairer complexity classes in Turing Machine. We start to investigate, in particular, the deterministic and non-deterministic complexity of this model for various natural problems. We then further study the alternating complexity of the model and find some surprising results, such as 3SAT can be recognized in near-constant steps. Moreover, as the automatic relations used in the model are actually pre-set to be bounded, we also investigate what happens if we initially give the model a big enough "working space" instead. Finally, we establish some complexity results on various extensions of the model, such as allowing unboundedness and introducing randomness. For further discussion, we also revisit the addition machine by Floyd and Knuth, the precursor of our model. We not only positively answer some of their open problems but also investigate the relationship between their model and ours, specifically its connection to automatic functions concerning the number of registers.