🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.theory
Article #1798

Re: FSM's to RM's

#1798
From: Steve W McDougall
Date: Wed, 12 Jun 1991 11:46
18 lines
1178 bytes
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?
Technical Details
Message-ID: <2386@riddler.tegra.COM>
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!wang!tegra!mcdougal
References: <3032@puck.sw.mcc.com> <16926@helios.TAMU.EDU>

Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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