🚀 go-pugleaf

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