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