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 ( rs to rd ) ; → rd
  • JUMP-UNCONDITIONAL to instruction Iz
  • JUMP IF =0 to instruction Iz

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

Read more about this topic:  Counter Machine

Famous quotes containing the words problems with, problems, counter, machine and/or model:

    “I was a wonderful parent before I had children. I was an expert on why everyone else was having problems with theirs. Then I had three of my own.”
    —Adele Faber (20th century)

    “While the onset of puberty can vary by as much as six years, every adolescent wants to be right on the 50-yard line, right in the middle of the field. One is always too tall, too short, too thin, too fat, too hairy, too clear-skinned, too early, too late. Understandably, problems of self-image are rampant.”
    —Joan Lipsitz (20th century)

    “The technological landscape of the present day has enfranchised its own electorates—the inhabitants of marketing zones in the consumer goods society, television audiences and news magazine readerships... vote with money at the cash counter rather than with the ballot paper at the polling booth.”
    —J.G. (James Graham)

    “Goodbye, boys; I’m under arrest. I may have to go to jail. I may not see you for a long time. Keep up the fight! Don’t surrender! Pay no attention to the injunction machine at Parkersburg. The Federal judge is a scab anyhow. While you starve he plays golf. While you serve humanity, he serves injunctions for the money powers.”
    —Mother Jones (1830–1930)

    “The Battle of Waterloo is a work of art with tension and drama with its unceasing change from hope to fear and back again, change which suddenly dissolves into a moment of extreme catastrophe, a model tragedy because the fate of Europe was determined within this individual fate.”
    —Stefan Zweig (18811942)