Talk:Register machine
From Wikipedia, the free encyclopedia
Contents |
[edit] PLEASE NOT DESTROY THE RM SIMPLICITY!!
Register Machine is a Turing Machine equivalent, to be SIMPLE TO USE. People reading this article need to see this simplicity (not prolixity!). Register Machine is a alternative (for Tuting Machine and other exotic equivalents) to be simple on show or scripting "abstract machine algorithms".
A program on a Register Machine is a SIMPLE SCRIPT! like a "ultra-RISC instruction set" assembly language...
This article is not a good place to show tables and long descriptions on "Turing-like style tables"!
Examples of clean styles:
State Type Reg Pass Fail
S0 DEC 1 S1 S2
S1 INC 0 S0 -
S2 HALT - - -
or, for wiki style,
- DEC 1, S2, S3
- INC 0, S1
- HALT
or, like on Assembly language article:
| Addr | Label | Instruction |
|---|---|---|
| 0 | begin | DEC (r1, begin, end) |
| 1 | INC (r0,begin) | |
| 2 | end | HALT |
See (for used style) ex. http://cs.wwc.edu/~aabyan/LABS/AR/RegisterMachine.html
-
- This model cited above is really a complex RAM Random access machine with accumulator etc. or possibly a RASP Random access stored program machine model. Observe that some commentators call these "register machines". Perhaps a better name for the primitive 2-3 instruction machine is a "counter machine." wvbaileyWvbailey 03:54, 17 October 2006 (UTC)
- the citation is for "style exemple" only. On the example scripts here, by the (stable) "Old Definition" (only by the your new def.), there are 2 registers (is not memory access).
- This model cited above is really a complex RAM Random access machine with accumulator etc. or possibly a RASP Random access stored program machine model. Observe that some commentators call these "register machines". Perhaps a better name for the primitive 2-3 instruction machine is a "counter machine." wvbaileyWvbailey 03:54, 17 October 2006 (UTC)
- At the article supplement Register machine models you will see a large collection of various models with instruction sets in much the same format you propose above. I can clean up the few that are not obvious and put them into tabular form. wvbaileyWvbailey 04:10, 17 October 2006 (UTC)
- Please sign your postings. wvbaileyWvbailey 03:35, 17 October 2006 (UTC)
- The model you propose for an RM is not "the correct" one: please observe that the three-parameter (DEC r1,xxx,yyy) and two-paramenter (INC r1,xxx) instruction set you propose (the one that was here originally) is neither "most common" nor the "most atomized". It uses a form of Turing-like state table rather than the sequential or "program-like" listing, i.e. instructions that follow in numerical order, one after the other, unless a conditional "jump" causes the program to "jump" out of order. [This model was proposed by Wang in 1957 or so]. Some versions of the Lambek-like "abacus machine" (1961) seem to use this binary-ternary form, but most others do not. One of the very significant, salient features of most models is sequential program flow -- so only single-parameter -- i.e. INC h -- and dual-parameter -- i.e. JZ h,xxx -- instructions are required. [And, in carefully-wrought cases such as the Schönhage models, NO parameters at all are required!] Please obtain and read the references cited to see how widely-variable the so-called "register machine" model really is. And refer to the link Register machine models. wvbaileyWvbailey 03:50, 17 October 2006 (UTC)
- see the first table-style example (above), all are 3 parameter (reg,pass,fail) instructions, but if the parameter have a is a Default_(computer_science)#Computer_language_defaults, we can write the instruction omitting the parameter ("omitting" is a style issue). Is not the case of OTHER model, it is a EXAMPLE OF other (not pulluted) style for "scripting".
-
-
- This part of the discussion is a waste of time. Read the history: the model was created through the work of Wang, the various German authors, and Shepherdson-Sturgis in part to allow for sequential instructions, like a typical computer, where the next instruction is assumed to be in numerical sequence. Lambek 1961 and Minsky 1961 departed from this, but by 1967 Minsky had returned to the sequential form. These are the facts, and this is the way the article is going to stay. I cannot rewrite from your desires, only from the facts as they appear in the literature. wvbaileyWvbailey 20:43, 22 October 2006 (UTC)
- Your on "Turing-like style tables" are waste of wikipedia article space. Please, the focus here is ONLY STYLE, for readers, for better presentation. PS: other parts of article are better with your 22/Oct/06 updates.
- This part of the discussion is a waste of time. Read the history: the model was created through the work of Wang, the various German authors, and Shepherdson-Sturgis in part to allow for sequential instructions, like a typical computer, where the next instruction is assumed to be in numerical sequence. Lambek 1961 and Minsky 1961 departed from this, but by 1967 Minsky had returned to the sequential form. These are the facts, and this is the way the article is going to stay. I cannot rewrite from your desires, only from the facts as they appear in the literature. wvbaileyWvbailey 20:43, 22 October 2006 (UTC)
-
[edit] Old Definition (put back!??)
A register machine consists of a finite set of registers r0 ... rn, each of which can hold a non-negative integer, and a finite list of instructions I0 ... Im. Each of the instructions in this list is one of the following:
INC (j, k)— increment the value of register rj by 1, then jump to instruction Ik.DEC (j, k, z)— check if the value of rj is zero. If so, jump to instruction Iz; otherwise, decrement rj by 1 and jump to Ik.HALT— halts the computation.
- I don't know what to say except: other readers don't agree with you. And the research into the literature does not back up your claim above. There are many versions of "the register machine", as noted in the introduction. The historical research remains as given in the article. Just recently I ran into "the abacus machine", again, in a new form in a book dated 2002 (not 1961 where it first originated with Melzak and Lambek). This is a survey article, not a push for one instruction set or another. I'm sorry that the world of "register machines" isn't as easy as you want it to be. Also, please sign your posts. wvbaileyWvbailey 03:33, 17 October 2006 (UTC)
- Think about SIMPLICITY, to be more didactic and less academic.
- Simplicity is not good if it represents falsity. I cannot present a single model without presenting the others. You have some good points below (I think, I'm having trouble with your english -- see the discussion below) but this push is not one of them. To carry this part of the discussion on further is a waste of time. wvbaileyWvbailey 20:48, 22 October 2006 (UTC)
- Think about SIMPLICITY, to be more didactic and less academic.
[edit] Informal Definition
Here a sugestion to clean and simplify a key section, the Register_machine#Informal Definition. Please change/correct and update if there are consensus to clean it:
- Simplify
- Remove citations and notes (it is "Informal"!)
- To be didactic (and more informal)
- To be a "standard model" for ALL EXAMPLES into the article.
There are a lot of model variants; here we present the more usual model (there are no "standard model").
The register machine take primitive concepts from usual mathematical tools:
- a kind of variable, the registers: they are "placeholders" for any integer numbers. It is a place to store a value in machine's memory.
- a kind of function, the instructions: they relates each of its parameters (input registers) to one output (register), or to an action.
The machine is a "buzzy bee" abstract model: it executes a list of instructions, step by step (sequentially), and the controller of these steps is a special variable, the program counter (PC).
The instructions may be equipped with jump to step (goto) action, updating the counter. It may be also in the form of an IF-THEN-ELSE operation, in a conditional jump form.
... (putting all together) ...
Recipe example: ...
I fiddled with the content here (see below) to see what it might look like. Frankly, I don't think that more time spent on this would be a good use of my time -- I should be working on the content of other articles, not trying to polish this one to a ultra-bright shine, not trying to "word-smith" it to death, or as some folks say (quoting the Psalms): not "Gilding the lily" (trying to improve something that is pretty good to start with). This rewrite took me about 2 hours. The improvement in content is minimal. It might be better, it might not. Who knows?
-
- To be "simple and didactic" is very difficult, for me, for you, and for many others... here (on Talk) we can try.
Perhaps you should take this and rework it to your liking. Or start fresh. I'm not trying to be unkind, I appreciate your willingness to comment. But what you write you will have to bring up to good standard English prose, and you need to read the literature. There are just too many models -- for example, a very popular one is the "successor" model with instructions { CLR h; INC h; COMPARE h1,h2 }.
-
- The election of a "reference-model for this article" is arbitrary (not exist a standard, like ISO C prog. language). If the "successor" model is popular, it is a good choice! I think we need a reference-model to the article, for work on better style, good examples, etc.
- Sorry my english, not is my language... to be good is a big effort to me, then I prefer to be anonymous, using my ugly english-like language.
I created a new article, now blank, called "Counter machine". But I am unsure about moving things there, because so many articles, Google-pages, etc. use the words "register machine" synonymously with "counter machine." What do you think? Do you think that we should move a lot of the present article to the new "counter machine" page and just keep the generic "register machine model" information on the "register machine" page? I believe that this would simplify the presentation of both topics, and if so, I believe this should be done before more "polishing and word-smithing". wvbaileyWvbailey 01:34, 24 October 2006 (UTC)
-
- Terminology is another problem; I think the concepts are all here... my point is about relevance, article structure, style... the wiki redirections I think ok.
Perhaps a drawing would help, too. I can do drawings. wvbaileyWvbailey
-
- ops, we need before consensus on style... sugestion: please, first help us to try a more simple/didactic "Informal Definition" text... the drawings at the last... -- Ugly-en anonymous 24 October 2006
[edit] Informal example/description
The following is the description of a counter machine found frequently in the literature.
-
- Sugestion: if this counter machine is a good "reference model", let us put (only) here, on Talk, your formal description to not do mistakes on informal text and examples. -- Ugly-en anonymous 24 October 2006
The model begins with a collection of discrete but labelled locations usually called registers, the number of which ranges from one to infinity depending on the model.
- For example: a line of holes "h" dug in the ground labelled "0", "1", "2",...
The "computer" (a person or machine) follows a list of sequential instructions called the program. Some instructions are arithmetic in nature and at least one is a conditional goto. The number of instructions is very small -- from two to seven is pretty much the rule.
- Example 3-instruction set: { INCrement h; DECrement h; JZ h,xxx }. The first two are "arithmetic", the third is a "conditional jump-if-zero/empty to instruction xxx".
The computer is equipped with an unlimited supply of indistinguishable objects called counters.
- Example of counters: pebbles to throw into or remove from the holes
Given the arithmetic instruction "INC h" above, the computer adds one counter to (i.e. increments) the contents of register #h. Or, given "DEC h" and given that the register-hole is not empty, the computer removes a counter from (i.e. decrements) the register #h.
The model is equipped with at least one conditional goto (jump, branch) in the form of an IF-THEN-ELSE operation. When the computer encounters this instruction it tests the specified register "h" to see if #h is empty of counters.
- for example "JZ 1,4" means: Test hole #1: IF hole #1 is empty THEN the next instruction will be "4", ELSE it will continue on in sequence to the next instruction.
To "keep the place" in the program -- in case the computer is sleepy or needs to use the bathroom -- the computer is equipped with an instruction-counter (not to be confused with the counters/pebbles themselves). After every non-jump instruction the computer simply increments (adds 1 to the contents of) its instruction-counter. But after a successful conditional goto the computer "jams" the jump-address xxx into its instruction counter and the instruction instruction.
The various parts of the model are shown in this example that "clears to zero" register 1. Note how it does an "unconditional jump"-- by testing empty register 0.
| Program: | ||||||||||||
| Instruction number → | 1 | 2 | 3 | 4 | ||||||||
| Instruction → | JZ | DEC | JZ | H | ||||||||
| Register number → | 1 | 1 | 0 | |||||||||
| Jump-to instruction # → | 4 | 1 | ||||||||||
| Label | Instruction counter | reg 0 | reg 1 | Instruction number | Comments | |||||||
| start: | 0 | 2 | 1 | |||||||||
| clear_loop: | 1 | 0 | 2 | 1→2 | JZ | Jump fails: register #1 contains "2" | ||||||
| 2 | 0 | 2→1 | 2→3 | DEC | register #1 is decremented from "2" to "1" | |||||||
| 3 | 0 | 1 | 3→1 | JZ | Unconditional jump: reg "0" is empty | |||||||
| clear_loop: | 1 | 0 | 1 | 1→2 | JZ | Jump fails: register #1 contains "1" | ||||||
| 2 | 0 | 1→0 | 2→3 | DEC | register #1 is decremented from "1" to "0" | |||||||
| 3 | 0 | 0 | 3→1 | JZ | Unconditional jump: reg "0" is empty | |||||||
| clear_loop: | 1 | 0 | 0 | 1→4 | JZ | Register #1 contains "0": Jump succeeds: | ||||||
| done: | 4 | 0 | 0 | 4 | H | Machine is stuck in HALT |
-
- I think your tables are complex and difficult to understand... It is good for DEBUG not for (simple and didactic) presentation... -- Ugly-en anonymous 24 October 2006
- ... alternative example, on wikitable style:
| Addr | Instruction | Comments |
|---|---|---|
| 1 | JZ(1, 4) | ... |
| 2 | DEC(1) | |
| 3 | JZ(0,1) | ... |
| 4 | HALT | ... |
And comments about states outside table. PS: people use recipes, usual programmers and not-programmer-people can follow a simple recipe.
Running describe example (DEBUG EXAMPLE):
Starting with r0=0, r1=2 and counter=1 (go to addr 1).
| Counter | Notes |
|---|---|
| 1 | Jump fails: r1=2 |
| 2 | r1 is decremented, from "2" to "1" |
| 3 | Unconditional jump: r0=0 (is empty) |
| 1 | (clear loop) Jump fails: r1=1 |
| 2 | r1 is decremented, from "1" to "0" |
| 3 | Unconditional jump: r0=0 (is empty) |
| 1 | (clear loop) r1=0, Jump succeeds: |
| 4 | (done) Machine is stuck in HALT. |
[edit] Introduction review
Register machine and counter machine are not ONLY TO "study decision problems"... it is TODAY a didactic tool, and in the "FIRST DAYS" was a "laboratory" for basic design and architecture models, and basic concepts.
Sugestion: add paragraph about it.
PS: another important use (usual for programmers not mathematicians) is to reduce a language to a "register machine like" language, to demonstrate that the language is Turing complete.
In theoretical computer science a register machine is an generic class of abstract machine used to study decision problems, similar to how a Turing machine is used. It is called a register machine because in place of "tape" the model uses multiple, uniquely-addressed registers each of which holds a single integer.
There are a lot of "common logic implementation techniques" used (in the first times of) Computer architecture and CPU design, and many basic concepts was demonstrated on register machines, that is today also a didactic tool for these concepts.
There are at least 4 sub-classes found in the literature, here (...)
[edit] Terminology and relevance
What the relevance of this terms for wikipedia readers (not for Wvbailey or a scholastic/academic public)!?
- But as a writer for wikipedia please remember that we (this includes you) have to stick to the published literature. We cannot invent phrases or usages. Thus this article is a survey article of the literature. wvbailey
Google say:
about 1,230,000 for "Turing machine" about 719,000 for "Turing machines". about 741,000 for "Turing machine" computer about 535,000 for "Turing machines" computers about 61,400 for "Register machine" about 14,000 for "Register machine" turing about 39,200 for "Register machine" computer about 66,300 for "counter machine" about 22,400 for "counter machine" computer about 799 for "counter machine" turing about 36,800 for "program machine" . about 23,600 for "program machine" computer about 4,520 for "program machine" turing about 1,050 for "Minsky machine". about 643 for "Minsky machine" turing about 553 for "Minsky machine" computer about 599 for "abacus machine" about 203 for "abacus machine" computer about 126 for "abacus machine" turing 1 for "Shepherdson-Sturgis machine" about 20 for "Shepherdson machine" 2 for "Lambek machine" 1 for "Lambek machine" computer
That is:
- "Register machine" (free or in a computer or turing context) is a term with about 5,0% of frequence of use of the term "Turing machine". (and 5,3% a Computer context)
- "Counter machine" about 5,0% (but 3,3% in a Computer context)
- "Program machine" 3,0% (and 3,2% in a Computer context)
- "Abacus machine", "Shepherdson-Sturgis machine", "Lambek machine" and "Minsky machine" LESS THAN 0,1%.
- "Minsky machine" 0,09%
- "Abacus machine" 0,05% (and perhaps used in not-turing context)
- Shepherdson and Lambek: zero (no significance).
And for any other text corpus or terminological analysis:
"Turing machine", "Register machine" and "Counter machine" are the relevant terms.
"Abacus machine", "Shepherdson-Sturgis machine", and "Lambek machine" are all curious terminology (or mere scholastic/academic spam!).
-
- Truly these names are not spam. They are named for the authors who first published/proposed them in the 1960's, and they are in current use in text-books. Moreover, they specify precisely a sub-type of counter machine model. They are not exactly the same models! See below. wvbaileyWvbailey 18:46, 22 October 2006 (UTC)
Sugestions:
- to add new section for Notes, Curiosities or Terminology.
- use on introducion (first parags.) only the usual terms, not do span for other terminology.
I am having a hard time understanding your complaint. But I think you are making a good point. But I want to be sure I understand. My survey indicates that the following is the actual usage in the current literature, and I want to see if you would agree to the following (please note the links-- they show the structure of this set of articles):
Fundamentally there are only two classes of abstract machine models currently in use (cf van Emde Boas, for example):
1) the tape-based Turing machine model: This class includes the following:
-
- = { single tape, multi-tape, deterministic Turing machine, Non-deterministic Turing machine, Wang B-machine model, Post-Turing machine, oracle machine, Universal Turing machine etc. }
2) the "register machine" model: This is a class of machines that includes the following:
-
- = { 2.1 counter machine, 2.2 random access machine RAM, 2.3 Random access stored program machine RASP, 2.4 pointer machine }
- 2.1) counter machine model includes:
- = { abacus machine, Lambek machine, Melzak model, Minsky machine, Shepherdson-Sturgis machine, pointer-machine, program machine etc. }
- 2.2) Random access machine (RAM) model includes:
- = { any counter-machine model with indirect addressing but instructions in the state machine in the Harvard architecture, any model with an "accumulator" and with indirect addressing but instructions in the state machine in the Harvard architecture }
- 2.3) Random access stored program machine (RASP) model
- = { any RAM with program stored in the registers similar to the Universal Turing machine, i.e. in the von Neumann architecture }
- 2.4) Pointer machine model includes the following:
- = { Schonhage SMM, KU-machine, Knuth linking automaton }
As noted in 2.2) within the counter-machine generic model there are various sub-types, their classification depending on the number of parameters used. The way to figure this out formally is to actually build the models in an Excel spreadsheet (I've done this) and see how many operands (i.e. Excel cells) are required to specify an instruction. Here I am including the "jump-to" address as an additional operand. So for instance the Schonage model has no operands excepting the jump-to address in an extra goto instruction:
- 0- & 1- operand: Schonage model
- 1- & 2- operand: Minsky (1967) model
- 2- & 3- operand: Minsky (1961), Lambek (1961)
- 3- & 4- operand: Malzek (1961)
There are models with "convenience instructions" (e.g. unconditional-J xxx, CLR h; CPY a,b ) including in particular:
- 2-operand: Shepherdson-Sturgis (1963), Minsky (1967)
For example: The model you proposed is the 2- & 3- operand model of Minsky (1961) and Lambek (1961). This is an "abacus model" not a "program model"; see below.
Recommendations:
- Create a new page called "register machine". This will be a page that directs the reader toward the four generic sub-types -- "counter machine", "RAM", "RASP", "Pointer machine". I can probably move some of the contents of the current "register machine" to this page.
- Move the article now titled "Register machine" to new article called "Counter machine". This would become the new page. This move would include the supplementary page too.
With regards to "abacus machine" -- I was very surprised to find this name used in Boolos-Burgess-Jeffrey (2002), the 4th edition of a very famous text that has been around for the past 40 years! But that is the formal, technical name of the model that you proposed. Lambek first proposed it in 1961. The Lambek "abacus" model is not a "program machine", it is an "abacus model". The difference is in the abacus machine the "next address" is specified as an additional parameter.
To serve the readers we need the article to define all these. This is a service to the readers. Again, there is no "best" or "most common" model -- who would be the little tin god who says so? Again this is a survey article -- it surveys the literature. It follows the usage of the van Emde Boas survey very closely. Please you must understand that I have read all these paper, and I have all these papers before me. I am not making this up. wvbaileyWvbailey 18:20, 22 October 2006 (UTC)
-
- Thanks for good explanation. I need time to read and check... You show what is relevant, what need emphasis on the article!
- ... I want to work (and/or to help on a wikibook if you have a lot of material to use)... but without "style disputes" here (!) -- on wikipedia articles, I think, we need not prolixity or excess of academic notes (on wikibooks it is ok). See (technical) featured articles... Technical writing is "translating technical ideas into words that a specific audience will understand" (and understand what is relevant without waste time). PS: the lacks focus (several irrelevant digressions) was a item why Algorithm was removed from featured arts.
-
-
- Ahh, but if you look at the history of "algorithm", I was the writer who added all the in-line citations, the history section, etc. Recently someone gave it an "A" rating. So "algorithm" is on its way back (also -- the grader did comment that the article kind of wandered away; I've meant to ask for more critique. I have expertise only in the first 1/2 of the article, not the later part with no in-line citations). The main objections of all the people who are "rating" the articles such as "algorithm" have been their lack of in-line citation and references (and such citations are policy, and wiki has put on a big push for this). However, recently there has been a really big dispute (I stayed out of it) about the use of inline citations (i.e. "Soare (1995) p. 2") in technical articles. I completely agree that they "break up the flow". But right now in its not-mature form, wikipedia needs this sort of ultra-precise referencing. My proposal would be: that after the articles have "stabilized", someday the in-line references can be "hidden"; but if curious, the reader can "reveal" them. There is definitely a variation in styles, and my style is to reference/cite everything I can. I've been "burned" enough on wikipedia with "needs citation" flags to now just put them in everywhere I can. I also use alot of direct quotes. I think wikipedia has a long way to go before it can say that it is something the reader trusts. First it needs good content, then secondarily it should worry about style.
-
-
-
- I do understand about the "prolixity" in this article and I'm wondering how to deal with it. Thus the split of "register machine" from "counter machine" would help, I believe. The "register machine" kind of "evolved" out of "couner machine" into RAMs and RASPs via starting with Wang and Minsky (1961), Melzak (1961) and Lambek (1961). Then Shepherdson-Sturgis (1963), in particular, discovered and surveyed the work of all the German researchers (I was surprised to find Rózsa Péter listed as one of them). They had worked on developing Turing-equivalent simple sequentially-executed instruction sets similar to computer instruction sets, but using accumulators (in particular). Thus was born the RAM-wanna-be, and Melzak actually added indirect addressing in his model and that was the real birth, I suspect. I don't have the German papers, can't find them. If a person were going to write a "huge" survey, they would need these papers. But anyway, that is probably the history in a nutshell of how the words "register machine" got confused with "counter machine". This sort of shows an approach I could take to split the article and reduce its 'prolixity'. wvbaileyWvbailey 14:32, 23 October 2006 (UTC)
-
[edit] Talk
[edit] "Standard Literature"
Hello, random unknown person. Timwi may not be the most courteous, but he was basically right. I've added a little bit of discussion of the "alternate" instruction set, and a reference to one of these pieces of "standard" literature. Andrew Rodland 10:38, 31 October 2005 (UTC)
[edit] Added Minsky model from 1967
I added this because the model presented (as a kind of Turing-machine with a state table rather than consecutive instructions of 1967) does not agree with the Minsky (1967) model. Maybe his thinking evolved. cf Post-Turing machine. Also Wang B-machine or some other appropriate name yet to be devised [now devised]. Forgot to sign original entry. wvbaileyWvbailey 21:27, 4 September 2006 (UTC)
[edit] Origin?
There are sources saying that the register machine was conceived by John C. Shepherdson and Howard E. Sturgis. They are not even mentioned in this article!
- Never heard of 'em. Minsky is given the credit for the idea. In his text, Minksy (1967) references Hao Wang (1954, 1957) (see Wang B-machine), says John Cooke and Wang suggested ideas for the chapter, and he references Stephen Kleene (1952) as having all the "basic results but without their formulation as computer programs." If you have a verifiable source, let us know. wvbaileyWvbailey 21:24, 4 September 2006 (UTC)
-
- Well, actually I only have what google will show in a second. Might be, that their contribution was the "Unlimited Register Machine" – nevertheless, here are some links:
- http://www.csse.monash.edu.au/~jnc/jnc-tutorial.pdf
- http://faculty.cs.byu.edu/~cgc/Research/Publications/StateNets.pdf
- http://logic.pdmi.ras.ru/~yumat/H10Pbook/commch_5.htm
- http://eom.springer.de/A/a011780.htm
- http://citeseer.ist.psu.edu/context/1447754/0
We have an interesting event here. The first two papers definitely sound like "the machine in question." Minksy's paper referenced in the article is 1961. His text is 1967. Minsky's text-references to himself include papers from 1956, 1959, 1961, 1962, 1963. The reference 1961 is the one cited in the article:
- Minsky, Marvin L. (1961) Recursive unsolvability of Post's problem of "tag" and other topics in theory of Turing machines, Annals of Mathematics 74, 437-454.
- Minsky, Marvin L.(1962) Size and structure of universl Turing machines using Tag Systems, Recursive Function Theory, Symposia in Pure Mathematics 5, American Mathematical Society.
The article cited in the first two references above is:
- Shepherdson, J, and Sturgis, H. (1963) Computability of Recursive Functions. Journal of the ACM, 10(2), pp. 217-255.
I have a good library at my disposal. I will (attempt to) track this down to the original source-level -- the original papers -- and see what is going on. My guess is Minsky (1961) will be referenced by Shepherdson and Sturgis (1963). But we shall see.
Even if we discover that S & S are citing Minsky -- we may find that they are contributing in the sense of making things clearer or introducing new ideas. Citing them as a reference won't hurt anyway. Plus a clarification here in wikipedia puts an end to the question. We just need to check the original papers for even prior refernces, for context etc.
(There is something wrong with Monash's discussion of "the machine" -- he cites the instruction set:
-
- Z --> 0
- Z --> Z + 1
- If Z <> 0 GO to L
I don't believe this is sufficient. If he had used
-
- Z --> 0
- Z --> Z + 1
- If Za <> Zb GO to L
Then he would have what I call a "Peano-axiom machine". Minsky 1967 discusses this on page 211. Also in a problem on page 214 he proposes that "the student" find some other sufficient combinations of 3 operation types from the set { Z-->0, Z --> Z+1, if zero jump else decrement, if not zero decrement and jump, copy a --> b, If unequal then jump, 'repeat' } .) wvbaileyWvbailey 17:30, 5 September 2006 (UTC)
-
- Good luck! It's been some years since I actually worked through this stuff thoroughly, don't have time to do it in a proper fashion again right now (those three instructions seem not to be Turing complete; I guess the three you mentioned would do it, but I'm not sure). It would definitely be a good thing if you could clarify the origin and settle this issue once and for all.
I've found the two papers in question. A third -- Lambek, mentioned in the third ref. above (I had to locate the book and find the references in the bibliography) -- and possibly a fourth (Malzak) (ditto) are supposedly being dredged (sp? dug up) from deep in the stacks in the library because the volumes are "in storage".
The results of my search are peculiar. The quick version: ambiguous. I need to read the papers more carefully. Basically, Minsky refers back to Kleene as having suggested the notion of a "register-like" model. And indeed Minsky is referred to by Shepherdson and Sturgis but only as a conference-paper, not as a published paper. And in Minsky's own paper, Minsky's "machine" is just a small one-liner-thing, very precisely defined but very brief, a bit different than what is described in the wiki article: i.e. it's a two-register machine with two instructions { UP, IF ZERO JUMP ELSE DOWN }. The context is Hilbert's l0th problem/Diophantine equations. And Minsky is fooling around with an equivalent recursive process to show that Post's "tag" is undecidable:
- "Theorem Ia. We can represent any partial recursive function T(n) by a program operating on two integers S1 and S2 using instructions Ij of the form:
- "(i) ADD 1 to Sj. Go to Ij1.
- "(ii) SUBTRACT 1 from Sj, if Sj <> 0, and go to Ij1. Otherwise go to Ij2." (p. 449)
Without a doubt S & S are more in the spirit of "the machine in question". I really have to agree that they define "the machine" more in the form I can recognize. They observe that "this form is chosen for ease of programming... this set is equivalent to a smaller set" (p. 219 Note (1)):
-
- "(a) P(n): add 1 to the number in register n, i.e. <n'> = <n>+1
- "(b) D(n): subtract 1 from the number in register n, i.e. <n'> = <n>-1
- "(c) O(n): "clear" register n, i.e. place 0 in it, i.e. <n'> = 0
- "(d) C(m,n): "copy from rgister M into register n, i.e. <n'> = <m>
- "(e) J[E1]: jump to exit 1
- ("f) J(m)[E1]: jump to exit 1 if register m is empty" (p. 219)
To add to the confusion: the two papers referred to by Matiyasevich, both appearing in the Canadian Mathematical Bulletin (1961), vol. 4 i.e. Joachim Lambek and Z. A. Melzak that (apparently) propose a similar model. (Lambek's is "How to program an infinite abacus" and Melzak's is "A Note on Hilbert's Tenth problem").
And over and over I've encountered a reference to Shannon that I will have to explore. So many ideas, so little time. wvbaileyWvbailey 23:38, 6 September 2006 (UTC)
I now have both Lambek (1961) and Melzak (1961). There's no doubt in my mind now that the article needs to be rewritten to reflect all these various folks' contributions -- it definitely appears that, indeed, they were all working, directly or indirectly, on Hilbert's 10th problem. That Minsky and Lambek-Melzak all published "at the same time" is one of those weird events -- like Post and Turing. If anyone wants any four of these papers, or Wang's paper where he defines his Wang B-machine, lemme know at my talk page and I will send them to you via e-mail attachment (in .pdf format). wvbaileyWvbailey
[edit] Hint
There's an interesting model which is even closer to real world computers (it includes indirect memory access):
The Random-Access Stored-Program Machine by Calvin Elgot and Abraham Robinson
- I've got the paper in me hot little hands, but haven't quite gotten to the RAM and RASP models yet. I've put some stuff on the Talk:Random Access Machine's talk-page. But am crunching away at it. I've been working on a "heirarchy" on the Turing machine equivalents page, got trapped into "recursion" by Minsky's derivations of the mu-operator (icky). But thanks! wvbaileyWvbailey 15:32, 22 September 2006 (UTC)
- Cook's name has come up but not before 1970. I will need to research it. I have the paper Cook and Reckhow 1973. Reckhow was Cook's Master's student. Cook's treatments seem to reside in CS 230 Notes (UC Berkeley, 1970), CSC 2428S (U. Toronto, 1971), and "Linear time simulation of deterministic two-way pushdown automata" Proceedings of IFIP congress 71, Foundations of Information Processing, No year). But again this is ten years later than the work of Lambek, Minsky, Malzek and Shepherdson-Sturgis (never mind all the Germans plowing the ground in the mid-to-late 1950's, especially Péter.) But as we have coming to know, we can't be sure until we've dug as deep as we can go. wvbaileyWvbailey 16:10, 22 September 2006 (UTC)
-
- Apropos Cook being mentioned as an original contributor - I can't find that paper nor do I remember who wrote it, but I'm pretty sure that it said something about Shepherdson -kind of inventor-like, too. I'm sure that you already plowed the historical ground more thoroughly than the author of that paper and didn't think, that Cook was the very first one - I just thought it would be nice to include him in the reference list (being called an original contributor - haven't examined that, though) --217.236.253.187 22:35, 22 September 2006 (UTC)
- PS This Turing machine equivalents page rocks!
-
-
- There's a lot more to be found (with respect to RAMs and RASPs) on the talk page of Random Access Machine but I haven't gotten to digesting/grinding it down into a coherent form yet. Then comes Pointer machine. Sigh. So many machines, so little time. wvbaileyWvbailey 23:13, 22 September 2006 (UTC)
-
[edit] Forename
I'm pretty sure that Mr. Kaphengst was called Heinz.
Look here:
http://www.nist.gov/msidlibrary/doc/kirsch_1963_application_automata.pdf
It even refers exactly to the same paper.
Kaphengst, Heinz. "An Abstract Programmed Computer." ZEITSCHRIFT FUR MATHEMATISCHE LOGIK UND GRUNDLAGEN DER MATHEMATIK, 5:3-4 (1959) 366-379
Heinz Kaphengst published several papers together with Horst Reichel – they are sometimes mentioned as H. Kaphengst, Horst Reichel, which lead to other pages referring to him as "Kaphengst, Horst".
Sincerely, --217.236.235.98 16:27, 3 October 2006 (UTC)
- Excellent. We will refer to H. Kaphengst as Heinz then, until further evidence to the contrary. I'm a continent away from my books and sources at this time, so I can't double check. So far I have been unable to get copies of the German originals from their journals in my library at home. This sets me on a mission. (As I was researching I wrotedo down next to the reference H. R. as Horst Reichel but ... there may be errors in my reference or this reference, too.) This just makes the research more fun, actually. Thanks...wvbaileyWvbailey 18:05, 3 October 2006 (UTC)
[edit] How To
There are many questions about "how to" implement basic algorithms and/or transform a model into another.
... SEE Talk:Counter_machine
[edit] Anonymous
As you can see I have split the articles into two parts. I think this will be better. I have updated the abstract machine page to show the structure (taxonomy) of the articles. I have trimmed both register machine and counter machine articles.
-
- Ok, lets talk about Talk:Counter_machine, then, back here... conter machines are the "basic referential model".
If you are new to wikipedia: As this is wikipedia you are free to edit, and add, wherever and as much as you want. I am not "the gate-keeper", nor is anyone else. If you want to add something and the english is not perfect then just do it, and if I or someone else (everyone can edit) thinks it is worth staying here we will fix the english. If you take something away and I or someone disagrees someone may add it back or bring it to the talk page to discuss first. That can happen to you too. If you have a better format for tables, then go ahead and change them. For example, my shading seems too dark on the ones I did. I experimented with putting each parameter in its own box and labelling the columns. I do like my tables with the "run" -- or I can create "drawings" to do the same directly from EXCEL (they are much harder to read and take many more bytes, as they are .JPG drawings)-- but I agree with you that the tables or drawings should be combined with a list of the instructions and the program itself.
My style is many quotes and citations. Believe it or not, I actually try to write for young college students with very little logic or computer-science, or none at all. Or I write for interested high-school students, but I do not write for programmers. They don't need wikipedia. That's why I like the Melzak-Lambek "holes"-for-registers and "pebbles"-for-counters analogy. Anyone who has learned simple arithmetic can get the idea. See Talk: Busy beaver for an example of what I wrote for some young people who were frustrated by the (rather bad) article. wvbaileyWvbailey 23:45, 24 October 2006 (UTC)
[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:58, 13 November 2006 (UTC)
