Re: Making C compiler generate obfuscated code

On Tuesday 21 Dec 2010 at 17:25, George Neuner <gneuner2@comcast.net> wrote:
> >Equivalence of programs is undecidable, ...
>
> I'm not sure that's true ... at least in theory. Turing equivalence
> guarantees that any program can be expressed in the lambda calculus,
> and the Church-Rosser theorem proves that two lambda expressions which
> reduce to the same expression are equivalent.


Any program which takes no input and produces no output can only
do one of two things:


(a) Terminate.
(b) Not terminate.


So such a program is equivalent to either SKIP or ABORT.
If this equivalence were decidable, then termination would also be decidable.
But termination is undecidable (http://en.wikipedia.org/wiki/Halting_problem).


--
Martin


STRL Reader in Software Engineering and Royal Society Industry Fellow
martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
[Termination is undecidable in general given an arbitrary program and
arbitrary input, but frequently decidable for a specific program and
specific input. I'd think a program that takes no input would be
pretty easy to analyze. -John]

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