Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!samsung!emory!gatech!mailer.cc.fsu.edu!sun13!sun16.scri.fsu.edu!mayne
From: mayne@sun16.scri.fsu.edu (Bill Mayne)
Newsgroups: comp.theory
Subject: Re: FSM's to RM's
Keywords: finite state machines register machines
Message-ID: <3301@sun13.scri.fsu.edu>
Date: 24 Jun 91 18:44:14 GMT
References: <3032@puck.sw.mcc.com> <16926@helios.TAMU.EDU> <2386@riddler.tegra.COM> <1991Jun24.130028.19598@siesoft.co.uk>
Sender: news@sun13.scri.fsu.edu
Organization: SCRI, Florida State University
Lines: 79

In article <1991Jun24.130028.19598@siesoft.co.uk> huw@siesoft.co.uk (Huw Roberts) writes:
>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.
>
>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 <? PDA <? RM = TM

You can code the state of the TM in the instruction pointer of the RM,
so all you have to worry about is representing the content of the tape
and the position of the read/write head in a register.

Putting the first and second parts of your argument together, it is possible
to simulate a TM using just two registers. This is came as a surprise to
me when I first encountered these defintions and arguments.

>I'm afraid I don't know what a PDA is.  (Pseudo Deterministic Automoton :-) ?)

PDA = "push down automata", i.e. a one stack machine. The "<?" are then
strictly "<", and the only correction needed to the original posted order
was to make "RM = TM". A two stack machine is of course equivalent to a TM,
since two stacks can obviously be used to simulate a tape. (It is the reverse
which is just a little messy, but Turing's argument that a TM can perform
any effective computation is pretty convincing, without going into the detail
of proving that any give formalism is no more powerful than a TM.) In fact it
is more straight forward to simulate a two stack machine using a RM than to
simulate a TM directly, because stacks are easier to simulate than tapes.

One approach to the simulation is as follows. Note that since it is already
known that any number of registers is equivalent to two there is no need to
try to minimize the number of registers at this point. The top symbol of
each stack can be coded in a register. Since the stack alphabet is finite
the the RM can use a chain of decrement and test instructions to determine
the value of the top symbol, restoring the value by a chain of increments
and branching where ever it wanted to go on the symbol found after the
stack register being tested reaches zero. Another pair of registers can
be used to represent the rest of the two stacks. Numbering the alphabet
symbols 1 thru m the value of a stack register when the stack holds
n symbols, t(1) thru t(n), is:

  n
SUM t(i)*(m+1)^(i-1)
i=1

To push a number multiply by m+1 (a constant) and add the pushed value.
(The pushed value = the old value from the top register.)
To pop a value divide by m+1. The remainder is the new top value.
Multiplication and division (with remainder) are straight forward using
loops with increment and decrement.

It is not really necessary to separate out the top symbol from the rest of
the stack like this, but it makes the proof a little easier to follow, IMO.
Some students might worry about the horrible inefficiency of having to
take the modulo of the whole stack just to non-deterstructively examine
the top symbol. :-)

Bill Mayne