The Setting
Every recursively enumerable relation is the set of inputs on which some counter machine halts, and a Diophantine representation of describes that halting computation by polynomial equations in the input and auxiliary unknowns .
A Diophantine representation of is single-fold when each has exactly one auxiliary tuple , so the halting computation recorded in has to be one object fixed by . The item supplies that object: the run of a counter machine from given initial counter values, its first halting time, and a base of numeration fixed by the number of states and those values.
The Definition
Definition 1. Let be a set of states and a set of counters.
An instruction over and is an element of the set (1)✦ where is a counter and are destination states.
A counter machine over and consists of an instruction at each state , an initial state and a halt state , such that (2)✦
A configuration over and is a pair (3)✦ of a state and a vector of counter values.
The step of is the map from configurations to configurations given by (4)✦ where is the unit vector of counter .
The run of on initial counter values is the sequence of configurations (5)✦ with the -fold iterate of .
A number is the first halting time of on , and halts on at time , if (6)✦
The halting relation of is (7)✦
When is finite with elements and is finite, the base of numeration for initial counter values is (8)✦
In the paper, the result reads: a counter machine has finitely many states, with an initial state and a halt state , and finitely many counters with values in ; every state other than has one instruction or with its destinations, and the halt state has none; and for states and initial counter values .
What Is Checked
The definitions are stated over a set of states and a set of counters, both arbitrary, with counter values in , and the base of (8) over finite and .