On One Class of Counter Machines

摘要

In this paper, we are concerned with the properties of a certain class of "automaton" counter machines in which each transition is defined nondeterministically according to the control states and irrespectively of the data being handled. Automaton counter machines are useful as a general means for demonstrating the undecidability of a series of problems that can be modeled by these machines, in particular, this being so for interacting coloring processes, which are useful in modeling the movement of data of various kinds between the components of a distributed system.