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.
Hey, this is well written.
Out of curiosity, how do you feel about Rice’s Theorem?
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.