Xref: utzoo comp.theory:2105 sci.math:18039 sci.logic:1340
Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!wang!tegra!mcdougal
From: mcdougal@tegra.COM (Steve W McDougall)
Newsgroups: comp.theory,sci.math,sci.logic
Subject: Re: FSM's to RM's
Summary: I'm still unclear
Keywords: finite state machines register machines
Message-ID: <2386@riddler.tegra.COM>
Date: 12 Jun 91 11:46:00 GMT
References: <3032@puck.sw.mcc.com> <16926@helios.TAMU.EDU>
Reply-To: mcdougal@tegra.UUCP (Steve W McDougall)
Followup-To: comp.theory
Organization: Tegra-Varityper, Inc. Billerica, MA
Lines: 18

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?