Re: Are there any tools that can compare two source files

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
instructions/states.


In this context, equivalence is perfectly decidable by a program with
slightly more memory. Might take a while though.


Tim Josling


"Torben Ęgidius Mogensen" wrote:


> Sarath Kumar <sarath_kumar@mentorg.com> 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 (torbenm@diku.dk)

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