🚀 go-pugleaf

In article <3069@optima.cs.arizona.edu> kwalker@cs.arizona.edu (Kenneth Walker) writes:
>
>For the moment, lets assume our analysis routine manages to place a bound
>on the number of states (size of memory) that will exist in the compiled
>program and that the analysis program must itself execute within the same
>finite-state machine. Because the analysis routine must itself be coded
>in some of the states, it does not have enough states to represent the
>states of the program it is analysing. Is there any hope (in a theoretical
>sense) of a finite state machine computing interesting properties of
>an arbitrary finite state machine of its own size?
>


No. But, a finite machine of size X can solve the halting problem for
finite machines of size Y, supposing that Y is sufficiently smaller than X.
In practical terms, this means a cross-compiler on a CRAY might be able
to detect failure to halt in programs being compiled for a small micro.
But, the exact ratio between X and Y depends on your ingenuity,the
programming language, and  the class of programs you find interesting.