NORMA (Number Theoretic Register Machine) was defined by Bird in 1976. It is an alternative to the Turing Machine. It's advantages over the Turing Machine is that its design is closer to a modern computer and NORMA is considerably easier to program. I'm not about to hold this against Turing though! Other than cosmetic differences it is identical to the Turing Machine and all the other Turing Complete systems (Yes, even brainfuck)
NORMA is so called because it uses registers instead of the Turing Machine's tape. The registers can only contain integers but, there are as many registers as you need (i.e. infinite) and the registers are infinite in size. The two most important which are the X and Y registers. The X register is for input and the Y register is for output. At startup the X register contains the program and input and the rest of the registers are null.
The NORMA programming language defines only four instructions these are:
Jump on Zero: JMP0( {Register}, {line number} )
Increment Register: INC( {Register} )
Decrement Register: DEC( {Register} )
Unconditional Jump: GOTO {line number} )
NB The HALT instruction is given by instruction NORMA to jump past the end of the current program e.g. for a 5 line program GOTO( 6 ) or JMP0( {Register = 0}, 6 ) would halt the program.
Problem: NORMA can only take a single integer as input. How can this single number contain the entire program and it's input?
What we need is an unambiguous system of coding the programs and input. That is we need each and every possible NORMA program to have a unique integer. We can do this because NORMA's input register (X) is infinite. It's all very well to simply say that we number each possible program but that doesn't tell us anything about the coding system except that it may be possible.
The Solution: Product of Primes Notation.
This notation relies on the fact that any integer can be represented as the product of prime numbers such that no other combination of primes will be able to make that number. e.g. 54 = 21 * 33, 55 = 51 * 111.
Let each instruction (I) be numbered: JMP0 = 0, INC = 1, DEC = 2, GOTO = 3.
Let each register (R) be numbered: X = 1, Y = 2, A = 3, B = 4 ...
Let each line (L) be numbered sequentially.
Each instruction can then be uniquely coded with three numbers: (I, R, L)
These three can be uniquely expressed as 2I * 3 R * 5L
Thus JMP0( X, 10 ) => (0, 1, 5) = 40, INC( Y ) => (1, 2, 0) = 18
A program can now be represented as a series of integers. We need it to be represented as a single integer so we apply product of primes again. This results in the NORMA code (Ncode) of the program. This method will be shown for some of the example programs but it is generally too large for my calculator and computer (octave and MATLAB) to calculate easily.
Programming in NORMA may seem like pulling teeth but with a few stock procedures that can be cut and pasted into your program it will soon become a nice high (ish) level language; these stock procedures are known a MACROs. A few of these are listed below. You might like to come up with MACROs for WHILE loops, division and prime decomposition if you feel so moved (I'll probably add them later anyway, if no-one else does)
MACROs to Make NORMA more Useful (Higher Level)
Zero Register: A := 0
1: JMP0(A, 4)
2: DEC(A)
3: GOTO(1)
4: (HALT)
Ncoding this program:
JMP0(A, 4) => (0, 3, 4) = 33 * 54 = 16875
DEC(A) => (2, 3, 0) = 22 * 33 = 108
GOTO(A) => (3, 3, 0) = 23 * 33 = 216
Thus the Ncode is: 216875 * 3108 * 5216 = 105282 (approx. Thanks to pmartel)
Try this on your calculator! (/msg me if you get even an approximate answer)
Destructive Addition: A := A + B (B will be lost)
1: JMP0(B, 5)
2: INC(A)
3: DEC(B)
4: GOTO 1
5: (HALT)
Non-destructive Addition:
1: C := 0 (from above)
2: JMP0(B, 7)
3: INC(A)
4: INC(C)
5: DEC(B)
6: GOTO 2
7: JMP0(C, 11)
8: INC(B)
9: DEC (A)
10: GOTO 7
11: (HALT)
Assignment to Register: A := B
1: A := 0
2: A := A + B
3: (HALT)
Source:
Notes on Computing Machinery Lectures given by Dr. J.M. Bishop at Reading University.