RS -Machines with Almost Blank Tape
Calvin C. Elgot, Joseph D. Rutledge · Journal of the ACM · 1964
Finite automata which communicate with counters or with tapes on a single letter alphabet with end mark are studied.A typical machine system s~udied here consists of a family of machines; the finite automaton part of each of the machines is ideutical; each machine has one reset counter (Mmost blank loop tape) and one non-reset counter (ahnost blank straight tape) ; the first counter counts up to a, say, and the second comets up to b.For each pair of natural numbers a, b there is a machine of the system with counters running up to a, b respectively.The system "accepts" those pairs (a, b) such that the (a, b)-nmchine eventually halts, when started in standard position.Thus the system de* fines a binary relation on natural numbers.Some solvability and unsolvability results are obtained concerning the emptiness of the set accepted by a system or the emptiness of the intersection of the sets accepted by two or more systems.Some of the theorems strengthen results of Rabin and Scott [8].It is shown for a certain class of systems that the relations defined by them are exactly the same as those definable in the elementary theory of addition of natural numbers.For another class of systems it is shown that an intersection problem is equivalent to Hilbert's tenth problem.