next up previous
Next: Computational requirements Up: What has not Previous: Convergence of block

Automata which are necessarily infinite

The very most exotic applications of the theory of computation require computers which are infinite in extent, at least in principle. Otherwise one is dealing with a finite state machine which can presumably always be evaluated by an exhaustive enumeration. In practice, a large enough extent is sufficiently close to infinite, and supposedly any quirks of infinite machines can be approximated up to a point by making the finite machine large enough. Nevertheless, there are certain theoretical considerations which are practically equivalent to choosing a definition of infinity, for which finite approximations will definitely not suffice. In any event, think of how much more tractable analysis becomes when real numbers can be used freely rather than rational approximations.

To a certain extent, the problem which arises is not with the limiting behavior of an automaton as with describing that behavior. Some limits are complicated and have a complicated description, but others have an exceedingly simple description with respect to other terms of reference. The recognition of balanced parentheses is the classical example; their description by regular expressions is infinite, substantially a listing of cases, while their description by a ``context free language'' is very short. No matter that the automaton required in either case is the same, it is the difference in the length of the descriptions required by the two schemes which counts.

Then again, it is likely that the majority of limit sets will be horrendously complicated, no matter what representation is chosen for them. Wolfram repeatedly emphasizes this point.



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx