Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!rpi!batcomputer!cornell!rochester!fulk
From: fulk@cs.rochester.edu (Mark Fulk)
Newsgroups: comp.theory
Subject: Re: FSM's to RM's
Message-ID: <1991Jun13.154102.8494@cs.rochester.edu>
Date: 13 Jun 91 15:41:02 GMT
References: <16926@helios.TAMU.EDU> <2386@riddler.tegra.COM> <1991Jun13.122113.29912@sics.se>
Organization: Computer Science Department University of Rochester
Lines: 79

In article <1991Jun13.122113.29912@sics.se> bjornl@sics.se (Bj|rn Lisper) writes:
>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

I am guessing that a register machine is essentially the same thing as
a counter machine: a machine with a finite state control and some finite
number of registers capable of holding any natural number.  I assume that
at least the following operations are available: add 1 to register,
subtract 1 from register, branch if register == 0.  The following is
well-known from old literature:

Any Turing machine can be simulated by a 1-tape TM (using tracks for tapes
and markers for heads, sweeping the entire used portion of the tape once
per original operation).

An n-tape TM can be simulated by a 2n-stack PDA (each stack represents the
part of the tape that extends from the head in the corresponding direction;
the symbol under the head is in finite state control; moving the tape is
equivalent to a pop of one tape followed by a push onto the other).

An n-stack PDA can be simulated by an n+1-counter counter machine
(Each counter codes the corresponding stack via radix notation; the least
significant digit is the top of the stack; push is multiply by the radix
then add; pop is divide by the radix; the extra counter is needed to
implement multiply (by a specified constant, not a variable) and divide
(similarly)).

An n-counter counter machine can be simulated by an n-stack PDA (just
put a marker on each stack, push blank to add 1, pop to subtract 1,
test the top symbol for comparison to zero).

An n-counter machine can be simulated by a 2-counter machine (one counter
codes the n-counters c1, c2,... as 2^c1 * 3^c2 * ... * (n-th prime)^cn;
increment ci becomes multiply by the i-th prime number; decrement becomes
divide; test against zero is divide with a remainder check; this is due to
Marvin Minsky).

A 1-stack PDA accepts a context-free language.

A 1-counter machine cannot accept a bracket language with more than one
kind of bracket.  It can, however, accept a bracket language with just
one kind of bracket, since to do that, counting is sufficient.

Note that allowing the registers of a CA to contain integers instead of
just natural numbers makes no difference; we need only maintain the signs
in finite control.

So we have:

FSA < 1CA < 1PDA < 2CA == 2PDA == nCA == nPDA = 1-tape TM == TM == Cray XMP.

Basic reference: Hopcroft and Ullman.

Mark