I hadn’t thought about Rice’s Theorem in this context before but it makes a lot of sense.
I guess I would say that Rice’s Theorem tells us that you can’t computably categorize Turing machines based on the functions they describe, but since algorithmic similarity calls for a much finer classification I don’t immediately see how it would apply.
And even if we had an impossibility result of this kind, I don’t think it would actually be a deal breaker, since we don’t need the classification to be computable in general to be enlightening.
Thank you!
I hadn’t thought about Rice’s Theorem in this context before but it makes a lot of sense.
I guess I would say that Rice’s Theorem tells us that you can’t computably categorize Turing machines based on the functions they describe, but since algorithmic similarity calls for a much finer classification I don’t immediately see how it would apply.
And even if we had an impossibility result of this kind, I don’t think it would actually be a deal breaker, since we don’t need the classification to be computable in general to be enlightening.