Register Machine

1. Register Machines

Register machines operate on natural numbers , stored in idealized registeres using the following elementary operations:

• Add to the contents of a register (increment).
• Test whether the contents of a register is zero (test).
• Subtract from the contents of a register, provided the register is not empty (decrement).
• Jump to another instruction (goto).
• Conditional jump to another instruction (if_then_else_).

A register machine is specified by:

• Finitely many reigsters , each capable of storing a natural number.
• A program consisting of a finite list of instructions of the form , where for , the -th instruction is labeled . The instruction body takes the form:
  • : Add to the contents of register and jump to instruction .
  • : If the contents of is , subtract from and jump to ; otherwise, jump to .
  • : Halt the machine.

For example:

1.1. Configurations

A register machine configuration has the form where is the current label and is the current contents of .

means .

The initial configuration of a register machine is . A computation is a finance sequence of configurations starting at . A finite computation ends in a halting configuration . Alternatively, a computation may halt erroneously. For example:

Non-halting computations are computations which never halt. For example:

1.2 Graphical Representation

• One node in the graph for each instruction.
• Node labelled by the register of the instruction body. denotes the register contents at label .
• Arcs represent jumps between instructions.
• Initial instruction .

1.3 Partial Functions

Register machine computation is deterministic: in any non halting configuration, the next configuration is uniquely determined by the program. So, the relation between an initial and final register contents defined by a register machine program is a partial function.

A partial function from set to set is specified by any subset satisfying:

Notation:

• means .
• means .
• means .
• denotes the set of all partial functions from to .
• denotes the set of all total functions from to .

A function is total if it satisfies .

A partial function is (register machine) computable if there exists a register machine with at least registers such that for all and all :

The computation of starting with halts with if and only if .

2. The Halting Problem

The Halting Problem is a decision problem with:

• The set of all pairs , where is an algorithm and is some input datum on which the algorithm is designed to operate.
• The property holds for if the algorithm halts on input .

The halting problem is unsolvable. i.e., there is no algorithm s.t:

3. Numerical Coding of Pairs

For , define

• gives a bijection between and .
• gives a bijection between and .

It is enough to observe that:

• followed by number of s.
• followed by number of s.

4. Numerical Coding of Lists

Let be the set of all finite lists of natural numbers, defined by:

• Empty list: .
• List cons: , if and .

Notation: .

For , define by induction on the length of the list:

This gives a bijection from to as .

Thus .

For example, is coded as .

5. Numerical Coding of Programs

If is an RM program:

Then its numerical code is where the numerical code of the instruction body is:

Any decodes to a unique insturction :

• if then
• else . Let in:
  • if is even, then
  • else is odd, then let in

So any decodes to a unique program , called the register machine program with index . For example: