Re: infinite state machines

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."

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