Register Machines

A register machine is a specific type of abstract computer. For my main purposes, the point is not that it is a computer, but that we can simulate the computation of the machine, that is, that a machine computation specifies a procedure.

We shall define a register-machine program over an alphabet %$\mathcal{A}$%. Since it is rare that we shall consider machines over different alphabets at the same time, I usually omit mention of the alphabet.

A program is a set of instructions which are, it is very important to note, themselves strings over some alphabet. Instructions begin with a "natural number" %$L$% called the label.

Here are the five kinds:

1. %$L$% LET %$R_{i}=R_{i}+a_j$%
2. LET %$R_{i}=R_{i}-a_j$%
3. IF %$R_{i}=\box$% THEN %$L'$% ELSE %$L_0$% OR ... OR %$L_r$%
4. PRINT (print out the contents of register 0).
5. HALT

Definition. A register program is a finite sequence of instructions of forms 1--5 such that the %$n$%th one has label %$n$%, all jumps jump to instructions that exist, and the last instruction, and only the last instruction is HALT.

We can now introduce some abbreviations for instructions: GOTO L is L IF %$R_{i}=\box$% THEN L ELSE L OR L OR ... OR L

GOTO L IF %$R_i$% IS EMPTY, ELSE L'

We now have a slew of obvious definitions to make officially:

The procedure coded by program %$\mathcal{P}$% halts, produces output ... .

%$W\subseteq A^*$% is register decidable, register enumerable if ... . A register program register decides, enumerates if ...

A function is register computable and computed by register program %$\mathcal{P}$% if ... .

Nameless thesis: the sets of register computable sets and functions and register enumerable sets are interesting. The reason these are interesting is that no machine (in an intuitive sense) computes larger classes of such things, and all reasonable machines compute exactly these.

The reason these things are interesting is that they are robust. Anything you try leads to the same class.

Since these classes are interesting, we give them a name not specifically tied to register machines: they are the recursively decidable (decidable), recursively enumerable (r.e.), recursively computable.

Church's thesis: Recursive = computable. Once more, this isn't the sort of thing that can be proved. Our experience however, is that everytime someone gives a systematic general notion of a procedure on words, it is recursive.

Now, more notation: If %$P$% is a program and %$\zeta$% is a word in the language of the program, then
%$P:\zeta\longrightarrow $%halt means the program halts on input %$\zeta$%
%$P:\zeta\longrightarrow \infty$% the program doesn't halt on input %$\zeta$%
%$P:\zeta\longrightarrow \eta$%, where %$\eta$% is also a word in the language, means that the program halts after printing %$\eta$% and nothing else.

Some programs:
0 PRINT
1 GOTO 0
2 HALT
That program never halts and never prints anything on no input, it prints the input over and over if there is an input.

Let our alphabet be {a,b}. 0 LET %$R_{0}=R_{0}-a$%
1 LET %$R_{0}=R_{0}-b$%
2 IF %$R_0$% EMPTY GOTO 3 ELSE GOTO 0
3 HALT

This program blanks register 0 in the given alphabet. It should be clear how to modify it to work in any other given alphabet and to blank any given register.

We can now combine the above machines with a trivial machine to produce a machine that, given any input prints it then loops forever with no output.

Here's how: 0 PRINT

That looks like this:
0 PRINT
0+1 LET %$R_{0}=R_{0}-a$%
1+1 LET %$R_{0}=R_{0}-b$%
2+1 IF %$R_0$% EMPTY GOTO 3change to 4 ELSE GOTO 0+1
delete 3 HALT
0+4 PRINT
1+4 GOTO 0+4
2+4 HALT

From our present perspective, the main result of last semester is this:

The set of logical consequences of an enumerable set of axioms is enumerable. -- ProfessorShaughanLavine - 26 Jan 2005