Re: infinite state machines

scorp@btinternet.com (Dave Harris)
28 Oct 1999 02:06:42 -0400

          From comp.compilers

Related articles
infinite state machines karthik@cdotd.ernet.in (1999-10-21)
Re: infinite state machines jfflorio@acm.org (J. Florio) (1999-10-21)
Re: infinite state machines qjackson@wave.home.com (Quinn Tyler Jackson) (1999-10-21)
Re: infinite state machines bourguet@my-deja.com (1999-10-27)
Re: infinite state machines chstapfer@bluewin.ch (Christian Stapfer) (1999-10-27)
Re: infinite state machines mac@coos.dartmouth.edu (1999-10-27)
Re: infinite state machines scorp@btinternet.com (1999-10-28)
| List of all articles for this month |

From: scorp@btinternet.com (Dave Harris)
Newsgroups: comp.compilers
Date: 28 Oct 1999 02:06:42 -0400
Organization: Burry Holms Research
References: 99-10-104
Keywords: DFA

The word "unbounded" is usually better than "infinite". For example, a
Turing Machine has an unbounded tape. The part used can grow without
limit, but at any point it is finite. You could reasonably implement one
with a finite tape provided you could pause it and add more tape whenever
it ran out.


Many programming languages present a Turing Machine-like model, with
unbounded memory, as an abstraction to work to. For example Java carefully
avoids specifying the width of a reference and so the language definition
does not limit the amount of memory that can be addressed. Specific
implementations may have limits, of course.


A Turing Machine also has a finite state machine which reads the tape.
This division into a finite state part and an unbounded state part is
useful. You can think of any I/O port as accessing unbounded memory, and
if you include that memory then the total machine has unbounded state.


If you think of the Internet as a single, multi-processor computational
device, then it arguably can grow without limit as new processors and RAM
can be attached at any time. Perhaps one day we will connect it to some
galactic or universal network. It's hard to put a bound on the number of
states the Internet may eventually have.


    Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
            brangdon@cix.co.uk | And close your eyes with holy dread,
                                                            | For he on honey dew hath fed
  http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.