Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!sics.se!sics!bjornl
From: bjornl@sics.se (Bj|rn Lisper)
Newsgroups: comp.theory
Subject: Re: FSM's to RM's
Message-ID: <1991Jun13.122113.29912@sics.se>
Date: 13 Jun 91 12:21:13 GMT
References: <3032@puck.sw.mcc.com> <16926@helios.TAMU.EDU>
	<2386@riddler.tegra.COM>
Sender: news@sics.se
Followup-To: comp.theory
Organization: Swedish Institute of Computer Science, Kista
Lines: 27
In-Reply-To: mcdougal@tegra.COM's message of 12 Jun 91 11: 46:00 GMT

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