Re: Making C compiler generate obfuscated code

Martin Ward <martin@gkc.org.uk>
Wed, 22 Dec 2010 11:30:48 +0000

          From comp.compilers

Related articles
[10 earlier articles]
Re: Making C compiler generate obfuscated code DrDiettrich1@aol.com (Hans-Peter Diettrich) (2010-12-16)
Re: Making C compiler generate obfuscated code torbenm@diku.dk (2010-12-20)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2010-12-21)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2010-12-21)
Re: Making C compiler generate obfuscated code walter@bytecraft.com (Walter Banks) (2010-12-21)
Re: Making C compiler generate obfuscated code gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-12-21)
Re: Making C compiler generate obfuscated code martin@gkc.org.uk (Martin Ward) (2010-12-22)
Re: Making C compiler generate obfuscated code DrDiettrich1@aol.com (Hans-Peter Diettrich) (2010-12-22)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2010-12-23)
Re: Making C compiler generate obfuscated code torbenm@diku.dk (2011-01-04)
Re: Making C compiler generate obfuscated code gneuner2@comcast.net (George Neuner) (2011-01-06)
| List of all articles for this month |

From: Martin Ward <martin@gkc.org.uk>
Newsgroups: comp.compilers
Date: Wed, 22 Dec 2010 11:30:48 +0000
Organization: Compilers Central
References: 10-12-017 10-12-033 10-12-035
Keywords: code, design, theory
Posted-Date: 23 Dec 2010 11:11:56 EST

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]



Post a followup to this message

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