Article View: comp.theory
Article #1798Re: FSM's to RM's
From: Steve W McDougall
Date: Wed, 12 Jun 1991 11:46
Date: Wed, 12 Jun 1991 11:46
18 lines
1178 bytes
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!mcdougalReferences:
<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