Counter Machine - Problems With The Counter Machine Model

Problems With The Counter Machine Model

The problems are discussed in detail in the article Random access machine. The problems fall into two major classes and a third "inconvenience" class:

(1) Unbounded capacities of registers versus bounded capacities of state-machine instructions: How will the machine create constants larger than the capacity of its finite state machine?

(2) Unbounded numbers of registers versus bounded numbers of state-machine instructions: How will the machine access registers with address-numbers beyond the reach/capability of its finite state machine?

(3) The fully reduced models are cumbersome:

Shepherdson and Sturgis (1963) are unapologetic about their 6-instruction set. They have made their choice based on "ease of programming... rather than economy" (p. 219 footnote 1).

Shepherdson and Sturgis' instructions ( indicates "contents of register r"):

• INCREMENT ( r ) ; +1 → r
• DECREMENT ( r ) ; -1 → r
• CLEAR ( r ) ; 0 → r
• COPY ( r_s to r_d ) ; → r_d
• JUMP-UNCONDITIONAL to instruction I_z
• JUMP IF =0 to instruction I_z

Minsky (1967) expanded his 2-instruction set { INC (z), JZDEC (r, I_z) } to { CLR (r), INC (r), JZDEC (r, I_z), J (I_z) } before his proof that a "Universal Program Machine" can be built with only two registers (p. 255ff).