The Setting
Let be a counter machine, started with the value in each counter . The relation “ halts from ” is recursively enumerable in , and by Matiyasevich’s theorem it is Diophantine. The question is whether it is single-fold: whether some Diophantine representation of it has exactly one auxiliary tuple for each from which halts.
A halting run of is a finite table that records, for each time up to the halt, the state and the values of the counters.
Counter Machines
An instruction over a set of states and a set of counters is the halting instruction, or with a counter and a next state , or with a counter and two next states, for a zero counter and for a nonzero one.✦ A counter machine with a finite set of states and a finite set of counters is an assignment of an instruction to each state, with an initial state and a halt state such that is the only state carrying the halting instruction.✦
A configuration of is a pair of a state and a vector of counter values.✦ For a counter , let be the unit vector of counter . The step of is the map on configurations that fixes when carries the halting instruction, sends it to when carries with next state , and, when carries , sends it to if and to if .✦ The run of from is the sequence of configurations , , with and the step of ; is the value of counter at time .✦
The machine halts at time from when (1)✦ and it halts from when it halts at some time ✦. The halting relation of is the set of vectors from which halts. The size bound of on is .✦
Single-fold Relations
A single-fold representation of a relation on tuples , for an index set , is a polynomial with integer coefficients in the input variables and finitely many auxiliary variables , all ranging over , such that (2)✦ A relation is single-fold when it has a single-fold representation, and is the class of single-fold relations.✦
The Witness System
For natural numbers and , the relation holds when every binary digit of is in .✦
A witness for is a tuple of natural numbers made of seven numbers , , , , , , ; for each state , a state string , a zero branch , a nonzero branch and a complement ; and three numbers , , for each in , where the clock is an index outside .✦ The base of is and its length is .
Each branch of an instruction has a destination and, in a witness , an arc weight: the one branch of at leads to its next state with weight , and at has a zero branch to of weight and a nonzero branch to of weight . The incoming weight of a state in is the sum of the arc weights of the branches with destination .✦ The increment weight and the decrement weight of a counter in are (3)
The witness system of on is the system of conditions on a witness , with the size bound of on , made of the scale conditions (4) the state conditions, for every state , with equal to for and to otherwise, (5) the branch conditions (6) for every state carrying , and for the other states; the counter conditions, for every , (7) the update and zero-test conditions, for every counter , (8) and the clock conditions (9)✦
The witness relation of is the set of pairs of a vector and a witness that solves the witness system of on .
For a witness with base , the digit of a natural number at position is .✦
The Claim
Theorem 1. Let be a counter machine with a finite set of states and a finite set of counters. Then (10)✦ and (11)✦ Let . If halts from , then some witness satisfies (12)✦ If and are witnesses with and in , then (13)✦ If and has length , then for every time , every state and every counter , the digits in the base of satisfy (14)✦ and halts from at time with (15)✦ For every positive integer , exactly one natural number satisfies (16)✦
In the paper, the result reads: for and a deterministic counter machine with instructions and and one halt state, whose counter starts at , a fixed coordinate of an input or , there is a finite system of polynomial equations with integer coefficients in and auxiliary natural numbers whose complete auxiliary tuple has exactly one solution when the machine halts and none when it does not.
What Is Checked
The theorem is stated over counter machines with instructions and and a single halt state, their runs and halting times from an initial counter vector , the witness system with its size bound , its base and its clock, and single-fold representations by polynomials with integer coefficients.