[rcme]

Regarding the definition of “observational equivalence”: I would love to see an example of two non-trivial statements that aren’t equal but are observationally equivalent. It seems impossible in almost any programming language.

[ajuc]

2 pure functions that calculate n digits of pi using different algorithms.

I guess you could exploit memory layout, different number of variables or timing attacks to distinguish them, but that's cheating IMHO. By that same method you could distinguish anything that compiles to different machine code.

[nitnelave]

You could argue that an implementation of a function to which you added asserts to make sure that logical invariants are maintained is different from the implementation without. The asserts will never trigger because they enforce properties that are always true for this function.

[Nevermark]

I think the interesting problem being described is:

Find two non-trivial algorithms so different that their equivalence is difficult to establish but which will always produce the same results.

Artificial code obfuscation techniques are not allowed. The algorithms can’t just be differently obfuscated versions of each other.

I.e. both algorithms should be in their simplest form given their respective approaches.