Re: infinite state machines

<karthik@cdotd.ernet.in> wrote in article: 99-10-104@comp.compilers...
> If we have finite state machines, is it possible to have 'infinite'
> state machines.
Depending on what one is willing to count as part of the "state" of a
machine, infinite state machines are very useful CONCEPTUAL models,
and not at all esoteric, as you seem to assume.


> One web site just mentioned that 'infinite state machines
> are conceivable but not practical'.
For the conceptual model of an automaton to be useful to us FINITE
human beings it must be specifiable with a FINITE amount of
information. If you just extend the model of a finite state machine
in a simple-minded way by allowing an infinite number of states, you
get an INFINITE specification for such an automaton: not very useful
for us humans.


But, as I said, as CONCEPTUAL models, some cleverly constrained types
of infinite state machines are neither exotic nor useless. Perhaps the
most important "infinite state" machine that is used in compiler
design theory is the pushdown machine: it has an infinite number of
states, because its stack component can be in an infinite number of
different states. By factoring the pushdown machine into a stack
(that can store an infinite number of symbols) and a finite state
control that bases its operation not only on its current state, and
the current input symbol but also on the symbol currently on the top
of the stack, you get a neat, compact, finite SPECIFICATION; even
though, that machine, if REALIZED in practice, would require an
infinite number of states. Which (probably) is not possible in this
world. (The number of particles in the universe is finite, as far as
we know.)


To sum up: Infinite state machines of various sorts are frequently
used idealizations that are very handy as CONCEPTUAL models but they
can only be approximated by finite state machines in practice. I hope
you realize that this situation is not exotic at all: applications of
mathematics in science and technology are full of similar
idealizations. For example, it would be extremely difficult for us to
reason, as we do, for example in calculus, if we refused to accept
idealizations such as irrational and transcendent numbers (the numbers
pi and e come to mind immediately, I suppose). Christian


P.S: Of course, any introductory book on automata theory would answer
your question, at least implicitly. They just do not normally belabor
the point, as I did here.


"A man who could give a convincing account of mathematical reality
would have solved very many of the most difficult problems of
metaphysics. If he could include physical reality in his account,
he would have solved them all."
        - G.H. Hardy: 'A Mathematician's Apology'

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