Re: generic state machine transaltion algorithm

Paul wrote:


> There is generic algorithm for translating between state machines so
> that programs that used to run on one state machine can be run on
> another via this translation process.


What do you mean by "state machine"? This term usually means
finite automata, which do not run programs, but recognize a class of
languages. It's possible to check whether two different specifications
describe the same regular language. But if by "state machine" you
mean computer processors, then, generally, the answer is "no",
since the translation process is undecidable (have a look at
semi-Thue processes for example, as well as many others rewriting
problems). On the other hand, there are some decidable subclasses,
which may turn out to be extremelly important for practical applications.
Search the ACM library for references addressing the area called
"binary translation". However, most of the so-called automatic
translators are in fact not so automatic, they often require tremendous
human support.


> So far as I know, all such processes are manual and non automatic.


And -- oversimplifying -- you are right.


> Is there any theory,


Yes: Term Rewriting Systems, automatic theorem proving, various
state space exploration and compression techniques (BDD etc.). As
far as I know there's no consistent, general theory, but many bricks
to build one are already available.


> or some one might have found a way to do it?


Well, in fact I'm going to do exactly this. :-)


        Piotr Wyderski

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