|[3 earlier articles]|
|Re: Are there any tools that can compare two source files email@example.com (2001-12-19)|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (Joachim Durchholz) (2001-12-20)|
|Re: Are there any tools that can compare two source files email@example.com (2001-12-20)|
|Re: Are there any tools that can compare two source files Martin.Ward@durham.ac.uk (2001-12-20)|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (2001-12-20)|
|Re: Are there any tools that can compare two source files email@example.com (Ira D. Baxter) (2001-12-22)|
|Re: Are there any tools that can compare two source files firstname.lastname@example.org (Tim Josling) (2001-12-22)|
|From:||Tim Josling <email@example.com>|
|Date:||22 Dec 2001 23:02:54 -0500|
|Organization:||Melbourne PC User Group|
|References:||01-12-027 01-12-058 01-12-092|
|Posted-Date:||22 Dec 2001 23:02:54 EST|
Not to forget of course that all 'real' computer programs have finite
memory and are thus actually state machines. To be a Turing machine
you have to have access to infinite memory, and that is very
expensive, even today.
If the size of memory including disk and tapes and registers is n bits,
then a deterministic program must either loop, halt or crash in 2**n
In this context, equivalence is perfectly decidable by a program with
slightly more memory. Might take a while though.
"Torben Ęgidius Mogensen" wrote:
> Sarath Kumar <firstname.lastname@example.org> writes:
> > Generalizing the problem refers to the problem of finding the
> > semantic equivalence of two programs. Is this possible?? As the
> > theorists go this is very tough and not possible in polynomial time.
> If the language is Turing-complete, equivalence is undecidable.
> This doesn't man that you can never the decide if two programs are
> equivalent, but it means that there are cases where you can't.
> Some languages, e.g., regular expressions, have decidable equivalence,
> but even for these, polynomial time normally isn't enough.
> Torben Mogensen (email@example.com)
Return to the
Search the comp.compilers archives again.