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?