Let’s start small. Since we are talking about algorithms (better yet, about programs of a universal Turing machine), what about if two programs can match the same input on the same output? Would that suffice as a definition of isomorphism, even if they have wildly different resource usages (including time)?
Yes—It’s not possible to decide, given two programs, if they have identical behavior. I think that’s okay here—the original poster asked for a definition of equivalence, not for a definition that was always decidable.
Let’s start small. Since we are talking about algorithms (better yet, about programs of a universal Turing machine), what about if two programs can match the same input on the same output?
Would that suffice as a definition of isomorphism, even if they have wildly different resource usages (including time)?
What if they don’t output anything?
Sadly, even that is unprovable—I believe there’s a way to convert a solution for this problem to one for the halting problem.
Of course you can still do it for a large fraction of functions you’re likely to see in real life.
Yes—It’s not possible to decide, given two programs, if they have identical behavior. I think that’s okay here—the original poster asked for a definition of equivalence, not for a definition that was always decidable.