The Setting
Take a recursively enumerable relation : the composite numbers, say, or the pairs with . The question is whether a machine that can only add one to a counter, or test a counter for zero and subtract one from it when it is not, recognizes : started with in of its counters and in the others, it should halt exactly when lies in .
The library reaches counter machines through stack machines and macro programs: a stack machine is translated into a macro program, whose instructions include multiply-add and division, and a macro program is compiled into a counter machine.
Counter Machines
An instruction with states in and counters in is the halting instruction, an increment of a counter with next state , or a test-and-decrement , with next state when is at and when is decremented.✦ A counter machine with states and counters consists of an instruction for each state , an initial state and a halt state , such that is the halting instruction exactly when .✦
A configuration of is a pair of a state and counter values .✦ Writing for with the value of replaced by , the step of is the map (1)✦ The partial step of is the map that agrees with on the configurations for which is not the halting instruction and is undefined on the others. A configuration is reached from in one or more steps, written , when arises from by applying the partial step at least once.
On an input , the configuration after steps is ✦, and halts at step on when (2)✦ The machine halts on when it halts at some step .✦
Macro Programs and Their Compilation
A macro instruction with states in and registers in is the halting instruction, a jump , an increment , a test , a multiply-add with a digit , or a division with a radix and a next state for each remainder.✦ A macro program with states and registers assigns a macro instruction to each . A macro configuration of is a pair of a state , or the mark of a halted program, and register values .✦ The macro step of from a state with values is the macro configuration (3)✦
The compiled machine of a macro program with an initial state is the counter machine whose counters are the registers in , a scratch counter and a zero counter .✦ Its states are a halt state and, for each and digits , the states , , , , , , and ; its initial state is .✦ A jump to a state is the instruction .✦ The instruction of at depends on as follows: (4)✦ At the other states, with , , and the next states read off , it is (5)✦ where ✦ and the finishing state is when is a multiply-add, when it is a division, and otherwise.✦ Where is not of the kind its row uses, the instruction at , , or is a jump to .✦
For a state of , values and , the configuration is in state with the registers in at , the scratch counter at and the zero counter at .✦ A macro configuration is represented in by and .✦
Stack Machines
The stack machines here work over the set of the four stacks , , and , the alphabet of two separators and the bits and , in this order✦, and a store that holds a symbol of or is empty, .✦ A statement over a set of labels is one of: a push of a symbol computed from the store onto a stack, a pop of the top symbol of a stack or a peek at it, setting the store from what was read, or an update of the store, each followed by a statement; a branch on the store between two statements; a jump to a label computed from the store; halt.✦ A stack machine with labels assigns a statement to each label . A set of labels supports when every jump in a statement with leads to a label in . Started at a label on , executes with the store empty, the main stack holding the code of the list in and the other stacks empty; it halts on when its run reaches halt.
The macro program of and has a register for each stack and a register for each input coordinate .✦ A symbol has the digit ✦; a digit has the symbol , and .✦ The states of , its labels, are for a statement and a store content , for a stack and a digit , and the labels of the start phase, which loads the input, among them for .✦
At , carries out the first instruction of and moves to , where is the statement that follows and is the new store. A push of onto stack is .✦ A pop from stack is , with the store set from for the remainder ; a peek is the same division, followed by , which applies when and goes on at .✦ Store updates, branches and jumps are instructions, a jump to going to , and halt is the halting instruction.✦
The start phase begins at .✦ For it pushes the separator by , divides by until it is , applying for each remainder and for each remainder , and then moves onto by and until the remainder is .✦ From it jumps to .✦
The statements of on are the statements that occur in for some , parts included✦, and a label of is good when it belongs to the start phase or its statement is one of them.✦ The restriction is the macro program on the finite set of good labels in which every jump to a label that is not good goes to instead.✦ The counter machine of , and is the compiled machine of with initial state ; its counters are the , the , and .✦ For , the counter input gives the value for each and every other counter the value .✦
The Claim
Theorem 1. Let .
(a) Let be a recursively enumerable relation. Then there is a counter machine with finitely many states, whose counters are for , , and , such that for every (6)✦
(b) Let be a stack machine with labels , let , and let be a finite set that contains and supports . Then for every (7)✦
(c) Let be a macro program with states , registers and an initial state, and let be its compiled machine. Then for every and every (8)✦
In the paper, the result reads: for and a recursively enumerable relation , there is a counter machine that, with its first counters set to and the rest to , reaches its halt state exactly when .
What Is Checked
Claim (6) is stated over recursively enumerable relations on and the halting of counter machines with finitely many states on the input , claim (7) over stack machines with a finite supporting set of labels and the counter machine compiled from the restriction , and claim (8) over the macro step of a macro program, its compiled machine and the representation of macro configurations.