A functional definition of algorithm similarity (number of same outputs on same inputs) disregards some "continuity"-ish assumptions: If A₁ gives the same answer as A₂ for many inputs, but for slightly perturbed inputs they give radically different outputs, I'd call those two algorithms very dissimilar.
This is maybe downstream from taking the functional and not algorithmic view on similarity: Wouldn't we want to *also* examine the traces we get?
Follow
Though this has problems with comparing across different computing paradigms (what's the trace of a λ-calculus expression to the one of a Turing machine computation?)
