meredith@puck.sw.mcc.com (LG Meredith) (06/05/91)
A lot of people have asked me what a register machine is. My naivete
led me to believe that this was common parlance. Sorry, just goes to
show how little i know about what i'm doing. Moving from the apology
to an exposition of register machines, Abelson and Sussman write:
"... we describe processes in terms of the step-by-step operation of a
traditional computer. Such a computer, or _register machine_,
sequentially executes _instructions_ that manipulate the contents of a
fixed set of storage elements called _registers_. A typical
register-machine instruction applies a primitive operation to the
contents of some registers and assigns the results to another."
Structure and
Interpretation of Computer
Programs
Harold Abelson and Gerald
J. Sussman with Julie Sussman
Hope this clears up the matter. cpm5479@zeus.tamu.edu (Christopher Menzel) (06/06/91)
In article <3032@puck.sw.mcc.com>, meredith@puck.sw.mcc.com (LG Meredith) writes...
=>
=>A lot of people have asked me what a register machine is. My naivete
=>led me to believe that this was common parlance.
Not so naive, it seems to me; I would say that it is common parlance
in the context of computability theory. Cutland's excellent text
{\it Computability} uses register machines as the vehicle into the
theory. It deserves mention that functions computable by register
machines = functions computable by Turing machines = recursive
functions = etc. mcdougal@tegra.COM (Steve W McDougall) (06/12/91)
In order to make sense out of the definitin of a register machine, I have to interpret it as follows: 1) An RM has a *finite* set of registers. 2) Each register can hold an *arbitrarily large* integer. If 1) doesn't hold, then an RM maps trivially into a turing machine, by assigning one register to each cell on the tape. If 2) doesn't hold, then an RM has only a finite number of states, and therefore it *is* an FSM. I also seem to recall that the following strict inequalities hold among the powers of various automata: FSM < PDA < RM < TM So is this how it is, or am I totally confused?
bjornl@sics.se (Bj|rn Lisper) (06/13/91)
In article <2386@riddler.tegra.COM> mcdougal@tegra.COM (Steve W McDougall) writes: >In order to make sense out of the definitin of a register machine, >I have to interpret it as follows: >1) An RM has a *finite* set of registers. >2) Each register can hold an *arbitrarily large* integer. >If 1) doesn't hold, then an RM maps trivially into a turing machine, >by assigning one register to each cell on the tape. >If 2) doesn't hold, then an RM has only a finite number of states, >and therefore it *is* an FSM. >I also seem to recall that the following strict inequalities hold >among the powers of various automata: > FSM < PDA < RM < TM >So is this how it is, or am I totally confused? It seems to me that if 2) holds, then any TM can be simulated by a RM, since any finite tape with symbols from a finite alphabet can be coded as a unique integer. Actually, just ONE arbitrary-size register should suffice. So I guess there's something fishy going on here? Bjorn Lisper
fulk@cs.rochester.edu (Mark Fulk) (06/13/91)
In article <1991Jun13.122113.29912@sics.se> bjornl@sics.se (Bj|rn Lisper) writes: >In article <2386@riddler.tegra.COM> mcdougal@tegra.COM (Steve W McDougall) >writes: >>In order to make sense out of the definitin of a register machine, >>I have to interpret it as follows: > >>1) An RM has a *finite* set of registers. >>2) Each register can hold an *arbitrarily large* integer. > >>If 1) doesn't hold, then an RM maps trivially into a turing machine, >>by assigning one register to each cell on the tape. > >>If 2) doesn't hold, then an RM has only a finite number of states, >>and therefore it *is* an FSM. > >>I also seem to recall that the following strict inequalities hold >>among the powers of various automata: > >> FSM < PDA < RM < TM > >>So is this how it is, or am I totally confused? > >It seems to me that if 2) holds, then any TM can be simulated by a RM, since >any finite tape with symbols from a finite alphabet can be coded as a unique >integer. Actually, just ONE arbitrary-size register should suffice. So I >guess there's something fishy going on here? > >Bjorn Lisper I am guessing that a register machine is essentially the same thing as a counter machine: a machine with a finite state control and some finite number of registers capable of holding any natural number. I assume that at least the following operations are available: add 1 to register, subtract 1 from register, branch if register == 0. The following is well-known from old literature: Any Turing machine can be simulated by a 1-tape TM (using tracks for tapes and markers for heads, sweeping the entire used portion of the tape once per original operation). An n-tape TM can be simulated by a 2n-stack PDA (each stack represents the part of the tape that extends from the head in the corresponding direction; the symbol under the head is in finite state control; moving the tape is equivalent to a pop of one tape followed by a push onto the other). An n-stack PDA can be simulated by an n+1-counter counter machine (Each counter codes the corresponding stack via radix notation; the least significant digit is the top of the stack; push is multiply by the radix then add; pop is divide by the radix; the extra counter is needed to implement multiply (by a specified constant, not a variable) and divide (similarly)). An n-counter counter machine can be simulated by an n-stack PDA (just put a marker on each stack, push blank to add 1, pop to subtract 1, test the top symbol for comparison to zero). An n-counter machine can be simulated by a 2-counter machine (one counter codes the n-counters c1, c2,... as 2^c1 * 3^c2 * ... * (n-th prime)^cn; increment ci becomes multiply by the i-th prime number; decrement becomes divide; test against zero is divide with a remainder check; this is due to Marvin Minsky). A 1-stack PDA accepts a context-free language. A 1-counter machine cannot accept a bracket language with more than one kind of bracket. It can, however, accept a bracket language with just one kind of bracket, since to do that, counting is sufficient. Note that allowing the registers of a CA to contain integers instead of just natural numbers makes no difference; we need only maintain the signs in finite control. So we have: FSA < 1CA < 1PDA < 2CA == 2PDA == nCA == nPDA = 1-tape TM == TM == Cray XMP. Basic reference: Hopcroft and Ullman. Mark
rockwell@socrates.umd.edu (Raul Rockwell) (06/14/91)
Mark Fulk: So we have: FSA < 1CA < 1PDA < 2CA == 2PDA == nCA == nPDA = 1-tape TM == TM == Cray XMP. Er... make that FSA == Cray XMP < CA == PDA == TM Godel coding allows you to code an arbitrary sequence of symbols (including integers) as an integer. On the other hand, a Cray XMP has very finite limits. -- Raul <rockwell@socrates.umd.edu>
fulk@cs.rochester.edu (Mark Fulk) (06/15/91)
In article <ROCKWELL.91Jun13210328@socrates.umd.edu> rockwell@socrates.umd.edu (Raul Rockwell) writes: >Er... make that > FSA == Cray XMP < CA == PDA == TM > >On the other hand, a Cray XMP has very finite limits. I think one is reasonably allowed to assume that the XMP has some dismountable disk drives or tape drives, and that the total quantity of tape truly available to a Cray is no less than that available to a TM. Conventionally, that is taken to be unbounded. Under those assumptions, Cray == TM. Mark
huw@siesoft.co.uk (Huw Roberts) (06/24/91)
mcdougal@tegra.COM (Steve W McDougall) writes: >In order to make sense out of the definition of a register machine, >I have to interpret it as follows: >1) An RM has a *finite* set of registers. >2) Each register can hold an *arbitrarily large* integer. >If 1) doesn't hold, then an RM maps trivially into a turing machine, >by assigning one register to each cell on the tape. >If 2) doesn't hold, then an RM has only a finite number of states, >and therefore it *is* an FSM. As I recall, a register machine is just as you describe. The program it runs consists purely of `add 1' and `subtract 1 and branch on 0' operations. I further recall that you can simulate a register machine with any given finite number of registers using a machine with only two registers by using one register to hold a coded version of the contents of the registers (2^a0 * 3^a1 * 5^a3, etc.) and using the other register as a working register. >I also seem to recall that the following strict inequalities hold >among the powers of various automata: > FSM < PDA < RM < TM >So is this how it is, or am I totally confused? I further remember that it is possible to simulate a TM using an RM. You code the contents of the tape in one register and the state of the machine in a second (use a couple more for working registers), so your equality could go like this: FSM <? PDA <? RM = TM I'm afraid I don't know what a PDA is. (Pseudo Deterministic Automoton :-) ?) Cheers, Huw -- If you want to flame, mail me directly and I'll summarise the best. Huw Roberts (huw@siesoft.co.uk) Siemens Nixdorf Information Systems Ltd.
mayne@sun16.scri.fsu.edu (Bill Mayne) (06/25/91)
In article <1991Jun24.130028.19598@siesoft.co.uk> huw@siesoft.co.uk (Huw Roberts) writes: >mcdougal@tegra.COM (Steve W McDougall) writes: > >>In order to make sense out of the definition of a register machine, >>I have to interpret it as follows: > >>1) An RM has a *finite* set of registers. >>2) Each register can hold an *arbitrarily large* integer. > >As I recall, a register machine is just as you describe. The program it runs >consists purely of `add 1' and `subtract 1 and branch on 0' operations. I >further recall that you can simulate a register machine with any given >finite number of registers using a machine with only two registers by using >one register to hold a coded version of the contents of the registers >(2^a0 * 3^a1 * 5^a3, etc.) and using the other register as a working register. > >>I also seem to recall that the following strict inequalities hold >>among the powers of various automata: > >> FSM < PDA < RM < TM > >>So is this how it is, or am I totally confused? > >I further remember that it is possible to simulate a TM using an RM. You >code the contents of the tape in one register and the state of the machine in >a second (use a couple more for working registers), so your equality could >go like this: > >FSM <? PDA <? RM = TM You can code the state of the TM in the instruction pointer of the RM, so all you have to worry about is representing the content of the tape and the position of the read/write head in a register. Putting the first and second parts of your argument together, it is possible to simulate a TM using just two registers. This is came as a surprise to me when I first encountered these defintions and arguments. >I'm afraid I don't know what a PDA is. (Pseudo Deterministic Automoton :-) ?) PDA = "push down automata", i.e. a one stack machine. The "<?" are then strictly "<", and the only correction needed to the original posted order was to make "RM = TM". A two stack machine is of course equivalent to a TM, since two stacks can obviously be used to simulate a tape. (It is the reverse which is just a little messy, but Turing's argument that a TM can perform any effective computation is pretty convincing, without going into the detail of proving that any give formalism is no more powerful than a TM.) In fact it is more straight forward to simulate a two stack machine using a RM than to simulate a TM directly, because stacks are easier to simulate than tapes. One approach to the simulation is as follows. Note that since it is already known that any number of registers is equivalent to two there is no need to try to minimize the number of registers at this point. The top symbol of each stack can be coded in a register. Since the stack alphabet is finite the the RM can use a chain of decrement and test instructions to determine the value of the top symbol, restoring the value by a chain of increments and branching where ever it wanted to go on the symbol found after the stack register being tested reaches zero. Another pair of registers can be used to represent the rest of the two stacks. Numbering the alphabet symbols 1 thru m the value of a stack register when the stack holds n symbols, t(1) thru t(n), is: n SUM t(i)*(m+1)^(i-1) i=1 To push a number multiply by m+1 (a constant) and add the pushed value. (The pushed value = the old value from the top register.) To pop a value divide by m+1. The remainder is the new top value. Multiplication and division (with remainder) are straight forward using loops with increment and decrement. It is not really necessary to separate out the top symbol from the rest of the stack like this, but it makes the proof a little easier to follow, IMO. Some students might worry about the horrible inefficiency of having to take the modulo of the whole stack just to non-deterstructively examine the top symbol. :-) Bill Mayne
puchm@cutmcvax.cs.curtin.edu.au (RichardPuchmayer) (06/25/91)
huw@siesoft.co.uk (Huw Roberts) writes: >I'm afraid I don't know what a PDA is. (Pseudo Deterministic Automoton :-) ?) Push Down Automaton. (A FSM with a stack). >Cheers, Huw Happy hunting, Richard. -- Richard Puchmayer == puchm@cutmcvax.cs.curtin.edu.au | Some of us are poets, Masters Student at Curtin University of Technology, WA.| some of us are not! -------------------------------------------------------+------------------------ I know nothing, so can hold no opinions for myself or others...