Re: FSM's to RM's

Article View: comp.theory

Article #1808

#1808

From: Raul Rockwell
Date: Fri, 14 Jun 1991 02:03

15 lines
1003 bytes

Mark Fulk:
   So we have:

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

Er... make that 
   FSA == Cray XMP < CA == PDA == TM

Godel coding allows you to code an arbitrary sequence of symbols
(including integers) as an integer.

On the other hand, a Cray XMP has very finite limits.

-- 
Raul <rockwell@socrates.umd.edu>

Technical Details

Message-ID: <ROCKWELL.91Jun13210328@socrates.umd.edu>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell

References:

<16926@helios.TAMU.EDU> <2386@riddler.tegra.COM> <1991Jun13.122113.29912@sics.se> <1991Jun13.154102.8494@cs.rochester.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell
From: rockwell@socrates.umd.edu (Raul Rockwell)
Newsgroups: comp.theory
Subject: Re: FSM's to RM's
Message-ID: <ROCKWELL.91Jun13210328@socrates.umd.edu>
Date: 14 Jun 91 02:03:28 GMT
References: <16926@helios.TAMU.EDU> <2386@riddler.tegra.COM>
 <1991Jun13.122113.29912@sics.se>
 <1991Jun13.154102.8494@cs.rochester.edu>
Sender: rockwell@socrates.umd.edu (Raul Rockwell)
Organization: Traveller
Lines: 15
In-Reply-To: fulk@cs.rochester.edu's message of 13 Jun 91 15: 41:02 GMT

Reply to Parent Message