Register machine

From Wikipedia, the free encyclopedia

In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to how a Turing machine might be used. All the models are Turing equivalent.

The register machine gets its name from its one or more "registers" -- in place of a Turing machine's tape and head (or tapes and heads) the model uses multiple, uniquely-addressed registers, each of which holds a single positive integer.

There are at least 4 sub-classes found in the literature, here listed from most primitive to the most like a computer:

counter machine -- the most primitive and reduced model. Lacks indirect addressing. Instructions are in the finite state machine in the manner of the Harvard architecture.
Pointer machine -- a blend of counter machine and RAM models. Less common and more abstract than either model. Instructions are in the finite state machine in the manner of the Harvard architecture.
Random access machine (RAM) -- a counter machine with indirect addressing and, usually, an augmented instruction set. Instructions are in the finite state machine in the manner of the Harvard architecture.
Random access stored program machine model (RASP) -- a RAM with instructions in its registers analogous to the Universal Turing machine; thus it is an example of the von Neumann architecture. But unlike a computer the model is idealized with effectively-infinite registers (and if used, effectively-infinite special registers such as an accumulator). Unlike a computer or even a RISC, the instruction set is much reduced in the number of instructions.

Any properly-defined register machine model is Turing equivalent. Computational speed is very dependent on the model specifics.

1 Formal definition
2 Problems with the counter machine model
3 Historical development of the register machine model
4 Precedence
5 See also
6 References
7 External links

[edit] Formal definition

No standard terminology exists; each author is responsible for defining in prose the meanings of their mnemonics or symbols. Many authors use a "register-transfer"-like symbolism to explain the actions of their models, but again they are responsible for defining its syntax.

A register machine consists of:

1 An unbounded number of labeled, discrete, unbounded registers unbounded in extent (capacity): a finite (or infinite in some models) set of registers r₀ ... r_n each considered to be of infinite extent and each of which holds a single non-negative integer (0, 1, 2, ...). The registers may do their own arithmetic, or there may or may not be one or more special registers that do the arithmetic e.g. an "accumulator" and/or "address register" (See Random access machine for more on this).

2 Tally counters or marks -- Discrete, indistinguishable objects or marks of only one sort suitable for the model. In the most-reduced counter machine model, per each arithmetic operation only one object/mark is either added to or removed from its location/tape. In some counter machine models (e.g. Melzak (1961), Minsky (1961)) and most RAM and RASP models more than one object/mark can be added or removed in one operation with "addition" and usually "subtraction"; sometimes with "multiplication" and/or "division". Some models have control operations such as "copy" (variously: "move ", "load", "store") that move "clumps" of objects/marks from register to register in one action.

3 A (very) limited set of instructions: The instructions tend to divide into classes. The instructions are drawn from the following sets to form "instruction-sets" that are subsets of the following, with this proviso: an instruction set must allow the model to be Turing equivalent, i.e. it must be able to compute any partial recursive function:

3.1 Arithmetic

Arithmetic instructions may operate on all registers or on just a special register (e.g. accumulator). They are usually chosen from the following sets (but exceptions abound):

Counter machine: { Increment (r), Decrement (r), Clear-to-zero (r) }
Reduced RAM, RASP: { Increment (r), Decrement (r), Clear-to-zero (r), Load-immediate-constant k, Add (r₁,r₂), proper-Subtract (r₁,r₂), Increment accumulator, Decrement accumulator, Clear accumulator, Add to accumulator contents of register r, proper-Subtract from accumulator contents of register r, }
Augmented RAM, RASP: All of the reduced instructions plus: { Multiply, Divide, various Boolean bit-wise (left-shift, bit test, etc.)}

3.2 Register-addressing method:

Counter machine: no indirect addressing, immediate operands possible in highly atomized models

RAM and RASP: indirect addressing available, immediate operands typical

3.3 Control:

Counter machine models: optional { Copy (r₁,r₂) }

RAM and RASP models: most have { Copy (r₁,r₂) }, or { Load Accumulator from r, Store accumulator into r, Load Accumulator with immediate constant }

All models: at least one conditional program "jump" (branch, goto) following test of a register e.g. { Jump-if-zero, Jump-if-not-zero (i.e. Jump-if-positive), Jump-if-equal, Jump-if-not equal }

All models optional: { unconditional program jump (goto) }

3.4 Input-output:

All models: optional

4 State register:

A special Instruction/Counter Register "ICR", finite and separate from the "program" registers above, stores/identifies the current instruction and its address to be executed. This register/counter is located in the finite state machine.

NOTE #1: The ICR is off-limits to the counter machine. It is NOT off limits to the RAM; indirection occurs by copying the contents of a register into the counter-portion of the ICR.
NOTE #2: The ICR is not the "program counter" (PC) of the RASP (or conventional computer). The PC register is just another register similar to the accumulator, but dedicated to holding the number of the RASP's register-based instruction. Thus a RASP has two "instruction/program" registers -- (i) the ICR (Instruction Counter-Register) for the instructions in the finite state machine and (ii) a PC (Program Counter) for the program located in the registers. (As well as a register dedicated to "the PC", a RASP will dedicate another register to "the Program-Instruction Register" (going by any number of names such as "PIR, "IR", "PR", etc.)

5 List of labeled instructions, usually in sequential order:

A finite list of instructions I₁ ... I_m. In the case of the counter machine, random access machine (RAM) and pointer machine the instruction (program) store is in the "table" of the finite state machine; thus these models are example of the Harvard architecture. In the case of the Random access stored program machine the program store is in the registers; thus this is an example of the von Neumann architecture. [[(See Random access machine for more on this).

Usually, like computer programs, the instructions are listed in sequential order; unless a jump is successful the default sequence continues in numerical order. An exception to this is the abacus (Lambek) counter machine model -- every instruction has at least one "next" instruction identifier "z", and the conditional branch has two. (Observe also that the abacus model combines two instructions JZ then DEC):

e.g. { INC ( r, z ), JZDEC ( r, z_true, z_false ) }.

See McCarthy Formalism for more about the conditional expression "IF r=0 THEN z_true ELSE z_false" (cf McCarthy (1960))

[edit] Problems with the counter machine model

See more about this at counter machine

No easy way to arrange for a stored program
No indirect addressing
The fully-reduced model is cumbersome

The first two problems do not plague the RAM and RASP because both are equipped with indirect addressing of their registers. And the RAM can take advantage of the notion of computed goto's and self-modifying instructions if it finds itself, caterpillar-like, turning into a RASP butterfly with the addition of instructions placed in the registers. (This usually calls for a few registers to be set aside as for e.g. "program counter" and "instruction counter".)

Usually the models have less-than optimum instruction sets. This is by design-- step-counting (when comparing algorithms) can become "dishonest" with clever, highly parallel instructions that are used more in one algorithm than in another (e.g. MUL done in one step -- for that matter, an entire program done in one step).

[edit] Historical development of the register machine model

Two trends appeared in the early 1950s -- the first to characterize the computer as a Turing machine, the second to define computer-like models -- models with sequential instruction sequences and conditional jumps -- with the power of a Turing machine, i.e. so-called Turing equivalence. Need for this work was carried out in context of two "hard" problems: the unsolvable word problem posed by Emil Post -- his problem of "tag" -- and the very "hard" problem of Hilbert's problems -- the 10th question around Diophantine equations. Researchers were questing for Turing-equivalent models that were less "logical" in nature and more "arithmetic" (cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218).

The first trend seems to have originated with Hans Hermes (1954) and Heinz Kaphengst (1959), the second trend with Hao Wang (1954, 1957) and furthered along by Joachim Lambek (1961), Z. A. Melzak (1961), Marvin Minsky (1961, 1967), and John Shepherdson-H. E. Sturgis (1963).

The last five names are listed by Yuri Matiyasevich (1993) (in that order, cf his chapter 5). He follows up with:

"Register machines [some authors use "register machine" synonymous with "counter-machine"] are particularly suitable for constructing Diophantine equations. Like Turing machines, they have very primitive instructions and, in addition, they deal with numbers" (cf Chapter 5).

It appears, remarkably, that Lambek, Melzak, Minsky and Shepherdson and Sturgis independently anticipated the same idea at the same time. See Note On Precedence below.

The history begins with Wang's model.

[edit] Wang's model: Post-Turing machine

Wang's work followed from Emil Post's (1936) paper and led Wang to his definition of his Wang B-machine -- a two-symbol Post-Turing machine computation model with only four atomic instructions:

{ LEFT, RIGHT, PRINT, JUMP_if_marked_to xxx }

To these four both Wang (1954, 1957) and then C.Y. Lee (1961) added another other instruction from the Post set { ERASE }, and then a Post's unconditional jump { JUMP_to xxx } (or the conditional jump JUMP_IF_blankto_xxx, or both) to make things easier (Lee named this a "W-machine" model):

{ LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }

Wang expressed hope that his model would be "a rapprochement" (p. 63) between the theory of Turing machines and the practical world of the computer.

Wang's work was highly influential. We find him referenced by Minsky (1961) and (1967), Melzak (1961), Shepherdson and Sturgis (1963). Indeed, Shepherdson and Sturgis (1963) remark that:

"...we have tried to carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested by Wang" (p. 218)

Martin Davis eventually evolved this model into the (2-symbol) Post-Turing machine.

[edit] Difficulties with the Wang/Post-Turing model

Except there was a problem: the Wang model (the six instructions of the 7-instructionsPost-Turing machine) was still a single-tape Turing-like device, however nice its sequential program instruction-flow might be. Both Melzak (1961) and Shepherdson and Sturgis (1963) observed this (in the context of certain proofs and investigations):

"...a Turing machine has a certain opacity... a Turing machine is slow in (hypothetical) operation and, usually, complicated. This makes it rather hard to design it, and even harder to investigate such matters as time or storage optimization or a comparison between efficiency of two algorithms. (Melzak (1961) p. 281)

"...although not difficult ... proofs are complicated and tedious to follow for two reasons: (1) A Turing machine has only head so that one is obliged to break down the computation into very small steps of operations on a single digit. (2) It has only one tape so that one has to go to some trouble to find the under one wishing to work on and keep it separate from other numbers" (Shepherdson and Sturgis (1963) p. 218).

Indeed as the following example shows, the work can be "complicated":

Example: Multiply a x b = c, for example: 3 x 4 = 12.

The scanned square is indicated by brackets around the mark i.e. [ 1 ]. An extra mark serves to indicate the symbol "0".

At the start of a computation, just as Shepherdson-Sturgis and Melzak complain, we see the variables expressed in unary -- i.e. the tally marks for a= | | | | and b = | | | | | -- "in a line" (concatenated on what Melzak calls a "linear tape"). Space must be available for c at the end of the computation, extending without bounds to the right:

			top	a	a	a		top	b	b	b	b		btm	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c
			[1]	1	1	1		1	1	1	1	1

At the end of the computation the multiplier b is 5 marks "in a line" (i.e. concatenated) to left of the 13 marks of product c.

			top	a	a	a		top	b	b	b	b		btm	c	c	c	c	c	c	c	c	c	c	c	c	c	c	c
								[1]	1	1	1	1		1	1	1	1	1	1	1	1	1	1	1	1	1

[edit] Minsky, Melzak-Lambek and Shepherdson-Sturgis models "cut the tape" into many

So why not 'cut the tape' so a, b and c are each infinitely long (to accommodate any size integer), and call these three tapes "Post-Turing (ie. Wang-like) tapes"? The individual heads will move left (for decrement) and right (for increment) In a sense the heads indicate "the tops of the stack" of concatenated marks. As was the case with Turing's original a-machine, the tapes can have a "left-end" symbol; this was done in the treatment of Hopcroft and Ullman (1979, p. 171ff).

Or, we just design our machine so that the test-for-zero and jump occurs before we decrement. Our machine asks the question: "Is the tape/counter empty? If so then I can't decrement, otherwise I can."

If we do this we don't need the extra mark to indicate "0", but we will need an extra "temporary" tape t to do a multiplication algorithm. And we will need an extra "blank/zero" register (e.g. register #0) for an unconditional jump:

At the start:
register 0:	[ ]
a = register 1:	1	1	1	[ ]
b = register 2:	1	1	1	1	[ ]
c = register 3:	[ ]
t = register 4:	[ ]

At the end:
register 0:	[ ]
a = register 1:	[ ]
b = register 2:	1	1	1	1	[ ]
c = register 3:	1	1	1	1	1	1	1	1	1	1	1	1	[ ]
t = register 4:	1	1	1	1	[ ]

We can write simple Post-Turing "subroutines" to atomize "increment" and "decrement" into Post-Turing instructions. Note that the head stays always just one square to the right of the top-most printed mark, i.e. at the "top of the stack". "r" is a parameter in the instructions that symbolizes the tape-as-register to be moved and printed or erased, and tested:

"Increment r" = PRINT_SCANNED_SQUARE_of_TAPE_r, MOVE_TAPE_r_LEFT; i.e. (or: move tape r's head right)

X+ r is equivalent to P r; L r

"Decrement r" = JUMP_IF_TAPE_r_BLANK(ZERO) TO XXX, ELSE MOVE_TAPE_r_RIGHT, ERASE_SCANNED_SQUARE_of_TAPE_rN; (or: move tape r's head left)

X- r is equivalent to J0 r,xxx; R r; E r

Indeed this is similar to the approach that Minsky (1961) took. He started with 4 left-ended tape-machine that:

"used the basic arithmetic device of the present paper. Then, two of the tapes were eliminated by the prime-factor method" (p. 438).

He then observed that:

"we may formulate these results so that the operations act essentially only on the length of the strings" (his italics, p. 449).

His first model, "1961" (it had changed by 1967) started out with only a single mark at the left end of each tape-as-register. The machine was not allowed to Print any marks, just move Left or Right and test for the mark = "1" in the following example. Thus the conventional Post-Turing-like instruction set went from

{ R; L; P; E; J0 xxx; J1 xxx, H }

to, for each tape-as-register:

{ R; L; J1 xxx, H }

where R can be renamed INCrement, R can be renamed DECrement, "J1" can be combined with "DEC" to create a non-atomized instruction, or can be kept separate and renamed Jump if Zero.

[edit] Melzak's model is different: clumps of pebbles go into and out of holes

Melzak's (1961) model is significantly different. He took his own model, flipped the tapes vertically, called them "holes in the ground" to be filled with "pebble counters". Unlike Minsky, Melzak allowed for "cuts" (proper subtraction of any length/count of pebbles) and "adds" (of any length/count of pebbles).

[edit] Lambek atomizes Melzak's model into INC and DEC-with-test

Lambek (1961) took Melzak's ternary model and atomized it down to the two unary instructions --X+, X- if possible else jump -- the exact same two that Minsky (1961) had come up with.

However, the Lambek model is not sequential -- both X+ and X- carry the identifier of the next instruction, and X- also carries the jump-to instruction of the zero-test is successful

[edit] Precedence

Minsky was working at the M.I.T. Lincoln Labs and published his work there; his paper was received for publishing in the Annals of Mathematics on August 15, 1960 but not published November 1961. While receipt occurred a full year before the work of Melzak and Lambek was received and published (received, respectively, May and June 15, 1961 and published side-by-side September 1961). That (i) both were Canadians and published in the Canadian Mathematical Bulletin, (ii) neither would have had reference to Minsky's work because it was not yet published in a peer-reviewed journal, but (iii) Melzak references Wang, and Lambek references Melzak, leads one to hypothesize that their work occurred simultaneously and independently.

Almost exactly the same thing happened to Shepherdson and Sturgis. Their paper was received in December 1961 -- just a few months after Melzak and Lambek's work was received. Again, they had little (at most 1 month) or no benefit of reviewing the work of Minsky. They were careful to observe in footnotes that papers by Ershov, Kaphengst and Peter had "recently appeared" (p. 219). These were published much earlier but appeared in the German language in German journals so issues of accessibility present themselves.

The final paper of Shepherdson and Sturgis did not appear in a peer-reviewed journal until 1963. And as they fairly and honestly note in their Appendix A, the 'systems' of Kaphengst (1959), Ershov (1958), Peter (1958) are all so similar to what results were obtained later as to be indistinguishable to a set of the following:

produce 0 i.e. 0 --> n

increment a number i.e. n+1 --> n

"i.e. of performing the operations which generate the natural numbers" (p. 246)

copy a number i.e. n --> m

to "change the course of a computation", either comparing two numbers or decrementing until 0

Indeed, Shepherson and Sturgis conclude

"The various minimal systems are very similar"( p. 246)

By order of publishing date the work of Kaphengst (1959), Ershov (1958), Peter (1958) were first. Does context matter? An answer would require close examination of the papers. Conclusions and opinions about this will be left to the reader.

[edit] See also

Counter machine

Wang B-machine
Post-Turing machine -- description plus examples
Algorithm

[edit] References

George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared -- the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines
Hopcroft, John, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
John McCarthy (1960), Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM, 3, 184-195 (April 1960).
Z. A. Melzak (1961, received 15 May 1961), An informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
Marvin Minsky (1961, received August 15, 1960). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Math 74: 437–455.
Marvin Minsky (1967). Computation: Finite and Infinite Machines, 1st ed., Englewood Cliffs, N. J.: Prentice-Hall, Inc.. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
Hermes, Hans Die Universalität programmgesteuerter Rechenmashinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.

Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23-25, 1954.