|generic state machine transaltion algorithm firstname.lastname@example.org (2004-09-21)|
|Re: generic state machine transaltion algorithm cfc@shell01.TheWorld.com (Chris F Clark) (2004-09-24)|
|Re: generic state machine transaltion algorithm wyderskiREMOVE@ii.uni.wroc.pl (Piotr Wyderski) (2004-10-02)|
|From:||"Piotr Wyderski" <wyderskiREMOVE@ii.uni.wroc.pl>|
|Date:||2 Oct 2004 01:11:54 -0400|
|Organization:||Faculty of Computer Science, University of Wroclaw|
|Posted-Date:||02 Oct 2004 01:11:54 EDT|
> 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
> 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. :-)
Return to the
Search the comp.compilers archives again.