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

## torbenm@eir.diku.dk (Torben Ęgidius Mogensen)

20 Dec 2001 00:35:22 -0500

*From comp.compilers*

| List of all articles for this month |

**From: ** | torbenm@eir.diku.dk (Torben Ęgidius Mogensen) |

**Newsgroups: ** | comp.compilers |

**Date: ** | 20 Dec 2001 00:35:22 -0500 |

**Organization: ** | Department of Computer Science, University of Copenhagen |

**References: ** | 01-12-027 01-12-058 |

**Keywords: ** | tools, theory |

**Posted-Date: ** | 20 Dec 2001 00:35:22 EST |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.