Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Re^2: Equivalency of Code

by ambrus (Abbot)
on Feb 07, 2005 at 10:26 UTC ( #428614=note: print w/replies, xml ) Need Help??

in reply to Re: Equivalency of Code
in thread Equivalency of Code

In the general case though, proving the functional identity of two pieces of code is equivalent to solving the halting problem, and thus infeasible (I think).

Indeed. If same($code1, $code2) could find out whether the $code1 and $code2 functions behave identically, then

sub f1 { "different"; } sub f2 { same(\&f1, \&f2) ? "same" : "different"; } f2();
would be a contradiction.

Replies are listed 'Best First'.
Re^3: Equivalency of Code
by bunnyman (Hermit) on Feb 07, 2005 at 16:09 UTC

    To spell it out explicitly, there is nothing that f2() can return that would be right.

    • If f2() returns "same", that means f2() and f1() should return the same things. f1() always returns "different" so this is incorrect.
    • If f2() returns "different", that means f2() and f1() should return different things. Now they are both returning the same thing, so this is also incorrect.

    The logical conclusion is that function same() does not exist.

      I disagree with your second idea. f2() and f1() returning the same thing is not the same concept as them having identical functionality.

      To Wit:

      sub f1 { rand; } sub f2 { srand; rand(1); }
      these functions are identical in function, but return different results for the same input.

        Two functions which are identical always return the same result for the same input. That's the definition of a function. Consider that the state of the computer is also an input to the function: if the random seed is the same for both functions, they do return the same results.

        If two functions have the same input (including the exact same environmental states) but do not return the same results (also consider changes to the environment to be "outputs") then they are not the same functions.

Re^3: Equivalency of Code
by adamk (Chaplain) on Feb 08, 2005 at 03:05 UTC
    That's a pretty big "in the general case".

    One can EASILY prove that the two following pieces of code are equivalent.
    my $foo = 1; my $foo = 1;
    So while you may not be able to work out if _any_ two pieces of code are equivalent, you can work out if _some_ two pieces of code are equivalent.

    As for the above example, it isn't really fair for the comparison function to have to compare itself.

    Generally most observes are given at least the countesy of being outside the situation being examined...

    So to summarise, there are ways to prove _some_ sorts of code are equivalent, just not _any_ code. And if you bias that process towards false negatives you stay pretty safe. (Accept false readings of "not equal" in exchange for certain results of "is equal")
Re^3: Equivalency of Code
by dragonchild (Archbishop) on Feb 07, 2005 at 17:08 UTC
    Actually, you'll hit a recursion limit before you run into your logical contradiction.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.


      You are assuming that same calls the functions it is passed as arguments.

      The theoretical same function cannot evaluate its arguments, as it cannot know that its arguments halt. After all, sub f1{ while(1) { } } and sub f2{ for(; ;) { } } should be considered the same...

      Also, for the purposes of computability "deciding" a problem means that the program must halt with an answer of either "yes" or "no". (Well, classically accepting or rejecting, but that is just semantics).

      Computer science is merely the post-Turing decline of formal systems theory.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://428614]
[1nickt]: ( Sometimes when idle I browse remote corners of the code repo at $work ... usually this yields knowledge of projects to decline and coworkers to avoid ... )
[LanX]: sure
[Corion]: 1nickt: Finding autobox in production would give me pause, yes
[LanX]: efficient survey
[MidLifeXis]: And under MINGW64_NT-6.1 MYHOST 2.6.0(0.304/5/3) 2016-09-09 09:46 x86_64 Msys there seem to be issues with escapes in external build tool calls.
[Corion]: I mean, it's a technical feat it achieves, but... why? ;)
[MidLifeXis]: And it also has the 0.14 version of the tarball in its manifest.
[LanX]: avoiding unreadable brackets
[MidLifeXis]: Although the previous one could be a b0rken PATH, I would need to dig for that.
[thezip]: I've got to go to meetings now. If anyone has further comments regarding Spreadsheet::XLSX deployment to Strawberry Perl 5.24.1, please /msg me -- thanks!

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (13)
As of 2017-03-23 17:24 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (291 votes). Check out past polls.