🚀 go-pugleaf

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.