Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!lll-winken!uunet!mcsun!ukc!stl!siesoft!huw From: huw@siesoft.co.uk (Huw Roberts) Newsgroups: comp.theory Subject: Re: FSM's to RM's Keywords: finite state machines register machines Message-ID: <1991Jun24.130028.19598@siesoft.co.uk> Date: 24 Jun 91 13:00:28 GMT References: <3032@puck.sw.mcc.com> <16926@helios.TAMU.EDU> <2386@riddler.tegra.COM> Sender: usenet@siesoft.co.uk (NNTP Poster) Organization: Siemens-Nixdorf Systems Development Group, UK Lines: 41 mcdougal@tegra.COM (Steve W McDougall) writes: >In order to make sense out of the definition 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. As I recall, a register machine is just as you describe. The program it runs consists purely of `add 1' and `subtract 1 and branch on 0' operations. I further recall that you can simulate a register machine with any given finite number of registers using a machine with only two registers by using one register to hold a coded version of the contents of the registers (2^a0 * 3^a1 * 5^a3, etc.) and using the other register as a working register. >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? I further remember that it is possible to simulate a TM using an RM. You code the contents of the tape in one register and the state of the machine in a second (use a couple more for working registers), so your equality could go like this: FSM