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.
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.
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.