Talk:Counter machine reference model

From Wikipedia, the free encyclopedia

Contents 1 Principles, please 2 No original research? 3 Terminology Talks 3.1 PC or ICR? 4 Alternative Base Model: "Successor" model 5 Explains 5.1 Formal Development: Reference Table Syntax 5.2 Other models and "reference models" 5.3 Overloading 6 Style for Algorithms!

[edit] Principles, please

The Occam's razor and Albert Einstein's maxim that "everything should be made as simple as possible, but no simpler". Programmers preffer to say KISS principle.

Mathematicians prefer the "do it right" method. I told you this would end in argument.wvbaileyWvbailey 20:38, 25 October 2006 (UTC)

Although it is poor practice to present a reader with stuff when the terms are not defined, the formal syntax was becoming burdensome and it was burying the tables. So I have moved the formal stuff toward the end so the tables come quickly to the eye.wvbaileyWvbailey 21:34, 25 October 2006 (UTC)

[edit] No original research?

Unfortunately, this article is close to violating WP:NOR. You MUST quote sources. You cannot derive ANYTHING. What you present must be there in the literature, somewhere. This is NOT the place to be writing a text or doing research or anything else like that. I am beginning to be concerned about your intent: if you are writing a book or thesis and using this as place to develop it you should go elsewhere. AND PLEASE SIGN YOUR POSTS: CREATE A NAME, use 4 tilde after it(Wvbailey 20:38, 25 October 2006 (UTC)). wvbaileyWvbailey 20:38, 25 October 2006 (UTC)

In addition to beiong questionable from a WP:NOR perspective, this article is not in the correct namespace. Wikipedia "conventions" (as this article claims to be) belong somewhere in the "Wikipedia" namespace. --Allan McInnes (talk) 04:19, 26 October 2006 (UTC)

I think you wrong, made a mistake with a "in construction article":

• The "reference model" is based on good cited researches. Wvbailey find a "base model" (avoiding the use of a "arbitrary model"): "The base model is derived from Minsky (1967), Lambek (1961) and in particular Shepherdson-Sturgis (1963 p. 225)".
• All Wikipedia:Featured articles have a "LITTLE original research": the Knowledge Organization (!). Article struture, choice of relevance of topics, examples, etc. was researched by a CONSENSUS PROCESS, and is a original research. All historically relevant Encyclopedias was made "relevant litle research" for Knowledge Organization.

-- User:Krauss 26 octuber 2006

---

Krauss, hi. I have opened a dialog with McInness re this article. Unless you are "anonymous" I don't think the problem is with your creating the article (maybe the article title is in a bad syntax but, hey, that can be fixed). The problem is more with the intent of "anonymous", and in my opinion, the "RefLib". If it were up to me I might (am unsure) eliminate the "RefLib" and keep the small table that defines and uses the "register-transfer sublevel" expression (see for example: C. Gorden Bell and Allen Newell (1971) Computer Structures: Readings and Examples, McGraw-Hill, New York.) Then in the Counter machine models I would use the "register-transfer" syntax to describe what the original authors had in mind.

Sorry, I think with a little example I can undertand better... see also my "Little original research" defence above.

The "register-transfer level" comes more from electrical engineering -- the usage is similar to this:

[ 3 ] → 5 =_def "The contents of register #3 are transfered to register 5"

This really means "replaces the contents of", not "adds to". This is true because electrical "bits" (i) first clear out the old bits and then (ii) put themselves into the new place.

You know -- it is a good thing I went through the example: The arrow of the counter-machine model is different than the "register-transfer" arrow. The counter machine model's usage of the arrow means truly transfer as in: "take from A and put into B". So: If you have a full beer-stein and I have a full beer-stein and I transfer my beer from my stein into your stein you will have beer all over the place plus a full stein. This rather unusual usage is okay because it appears in Melzak's (1961) pebble-and-hole model and in Boolos-Burgess-Jeffrey. wvbaileyWvbailey 20:53, 26 October 2006 (UTC)

I would have to re-read Bell and Newell carefully to be sure of their syntax (I hated it the first time 30 years ago, am no fan of theirs).

It will be didactic? (see changes, I use the term "formal semantic" for "not like assembler" descriptions... I think better find good "referential logic meta language" here on wikipedia (other article) to the "formal semantic". -- Krauss

Per a Bell and Newell example the syntax would look like this:

Example:

and → ( AC ← AC & M[ z ] )  ; is how they describe logical AND for a 12-bit PDP-8 like computer. The "M" designates "Memory", the "z" is a (in this case 12-bit) memory-pointer register, like an index register (the models here seem to be von Neumann, e.g. this is back in the PDP-8 days)

Ops, about use of AC here, see #Other_models_and_.22reference_models.22.

If Boolos-Burgess-Jeffrey 2002 were to describe an "AND(register z, AC, AC)" they would put the "transmit" (Bell and Newell terminology) arrow the other way, i.e. →. And they would put a "box" around the AC, i.e. [AC].

[ AC ] & [ z ] → AC

The above show why this is why this is so hard. There are no conventions, really.

... I think exist good mathematical "syntax conventions" on wikipedia...

I looked and didn't see any good ones. Most of them are the register-transfer type, and the counter-machine model is doing something different, as I noted above:

IF [ my_stein ] = [ your_stein ] = "full", THEN [ my_stein ] → your_stein = a mess + ( [ your_stein ] = "full" )

IF [ my_flip-flops ] = [ your_flip-flops ] = "full" = 11111111, THEN [ my_flip-flops] → your_flip-flops = ( [ your flip-flops ] = 11111111 )

wvbaileyWvbailey 20:53, 26 October 2006 (UTC)

So we kind of pick a source (e.g. Bell and Newell versus Boolos-Burgess-Jeffrey) and then define the syntax ourselves in "natural language". Yikes! wvbaileyWvbailey 15:11, 26 October 2006 (UTC)

Per the above examples we have to pick Melzak (1961) and Boolos-Burgess-Jeffrey. And this is not standard "logic": "logic" would use OR: i.e. OR(A,A) = A→A = A. The counter machine model works differently than "logic" because we start with INC and DEC: i.e. [A]→A = 2*[A]. wvbaileyWvbailey 21:06, 26 October 2006 (UTC)

Sugestion:

1. Finish a "first version" for this article
2. Use RefLib (or similar one) on the other "dependent articles"... It will be a big work.
3. Back here on Talk for see if we need MORE work ...

-- User:Krauss 26 octuber 2006

[edit] Terminology Talks

[edit] PC or ICR?

If "Instruction Counter Register (ICR)" ~= "Program Counter (PC)" THEN use the "more usual". [unsigned Krauss]

(Krauss, sign your posting so you don't look like "anonymous".) To answer your question:

I was trying to come up with a "name" for the finite state machine's (FSM) "instruction counter/register" -- the so-called "state register" (I hate that name but it is commonly used -- in fact the state of a computation is not just what is in the "state register", but rather what is in all the registers including the "ICR"). This is quite different from the RASP's special register -- a "program counter" that is pointing to an instruction in the registers. I.e. the RASP has two counter-registers: the base FSM "microprogram" instruction register "ICR" and the program-in-the-registers PC. wvbaileyWvbailey 15:39, 26 October 2006 (UTC)

Other possibilities: "SCR" for state counter-register,i.e. it may also be a counter that increments automatically, "FSMCR" "Finite state machine Counter-Register". wvbaileyWvbailey 15:48, 26 October 2006 (UTC)

[edit] Alternative Base Model: "Successor" model

The choice is arbitrary... but, we need a choice, not alternatives. If decide this, remove the other (and redo RefLib) -- Krauss

This is a tough one. Let me think on it for a while. Let's let it sit, as is, for little while -- I wish we had more input here. If you know of anyone who can give input get them to put something here on the page. A piece of me leans to the successor model, but because the "count-down loop-counter" is so common, and DEC is so useful, the first thing a person would do would be to create the subroutine for it. All the earliest models, especially Lambek, were DEC and INC.

The only real problem with DEC is what happens when the register is empty. That is why Minsky and Lambek (but not Sheperdson-Sturgis) started with just two instructions { INC 9r), JZDEC (r,z) }. For HALT, some models use an attempt to "drink beer from cup" & "cup" = "empty". But if you try to drink from an empty cup all you get is "beer=0". Hence the definition as it now stands on the page.wvbaileyWvbailey 18:34, 26 October 2006 (UTC)

Reference (Base) model:

This base model is used in the successor-Random Access Machine model (cf van Emde Boas 1992) and used e.g. by Schönhage (1980) in his development of the RAM0 and RAM1 models. It also is discussed in Minsky (1967) where he uses Jump-if-Not-Equal (JNE) rather than Jump-if-Equal (JE) but in context of the counter machine. Observe that it closely resembles the Peano axioms.

Observe that the instructions CLR and JE can be derived from the first base set, and if one were to use three successor-instructions one could derive DEC and JZ; for a demonstration see Footnote|Predecessor function.

As before, the model consists of a finite set of registers r₁ ... r_n, each of which can hold a non-negative integer, r₀ (always zero), and a finite list of instructions I₁ ... I_m. Each of the instructions in this list is one of the following:

• CLR(j) — clear to zero the value of register r_j, then go to the successor instruction:
• INC(j) — increment the value of register r_j by 1, then go to the successor instruction (e.g. instruction that is numerically next-in-sequence)
• JE (j, k, z) — if contents of register r_j = r_k then Jump to instruction I_z else go to the successor instruction
• HALT — halts the computation.

Formal Definitions:

Instruction	Effect on register	Effect on state-machine's Instruction Counter Register ICR
CLR ( j )	0 ? rj	[ ICR ] + 1 ? ICR
INC ( j )	[ r j ] + 1 ? rj	[ ICR ] + 1 ? ICR
JE ( j, k, z)		( ( rj =rj ) & ( Iz ) V ( ~(rj = 0) & ( [ICR] + 1 ) ) ? ICR

[edit] Explains

[edit] Formal Development: Reference Table Syntax

NEED THIS ON THIS ARTICLE??

Yes, but a reduced version. I will pick at it. wvbaileyWvbailey 18:13, 26 October 2006 (UTC)

Syntax:

The syntax is derived from Boolos-Burgess-Jeffrey (2002) (pp.45ff). It describes a form of register transfer operation. The meaning of the symbol → is derived from Melzak (1961) and used by B-B-J. For a discussion of the if-then-else construction see Footnote|IF-THEN-ELSE operator: { [ ], → }

• [ ] =_def the phrase "the contents of"
• → =_def the "transfer arrow" denotes "put into" in the sense of "add to"
• r =_def register with address/name/number "r". A "register" is both an address/name/number and a contents [ ]:

Example: [ 3 ] =_def "contents of register with address/name/number '3' "

• ICR =_def Instruction Counter-Register, the finite-state machine's state-register

Example: "[ ICR ] + 1 → ICR " is read in prose: "The contents of the Instruction Counter Register plus 1 is 'transferred to'/'put into'/'replaces the contents of' the Instruction Counter Register (ICR) ".

• +1 =_def successor function S(a) = a' = a+1 (See Footnote|Successor model)
• -1 =_def predecessor function pd(a') = a (See Footnote|Successor model)

Footnote:IF-THEN-ELSE operator:

in Minsky (1967):

" f = (if p₁ then e₁ else e₁)

"This expression means

"See if p₁ is true; if so the value of f is given by e₁. If p₁ is false, the value of f is given by e₂." (Minsky 1967 pp. 192ff: Conditional Expressions; The McCarthy Formalism)

[edit] Other models and "reference models"

• Counter machine the "main user" of RefLib.
• Register machine the "hub article" for other models. There are another "augmented models", and the respectives "reference models":
  • Pointer machine:Reference model (or RAMrefModel): augment the indirect addressing and the RefLib for it. Is used also on the Random access program machine.
  • Random access stored program machine:Reference model: base on the RAMrefModel.

[edit] Overloading

Today (and in a programming language context) is usual the function overloading, but on assembler languages, and until 1970s, the pratic was use of a lot of function names...

SUGESTION: overloading on RefLib, to be simple, and because models have prefixed number of parameters (not confusion). -- Krauss 27 octuber 2006

[edit] Style for Algorithms!

See Wikipedia:Algorithms on Wikipedia.

Sorry, but the above is bogus. I am sticking with the convention in Boolos-Burgess-Jeffrey (2002) because it is a convention to be found in a published text. wvbaileyWvbailey 20:57, 13 November 2006 (UTC)