In the general case, not necessarily for any subset, and this would apply to to non-functional algorithms as well. Just because I write a 'simple' for/while loop, that doesn't necessarily imply anything about the actual
At the end of the day, an algorithm is simply an unambiguous, executable, and terminating specification of a way to solve a problem. We may implement an algorithm by creating a physical or virtual machine that conforms to that specification, but even abstractions like Turing machines and lambda calculi are just attempts at creating a deterministic model that we can manipulate in order to understand the algorithm, which is an abstract specification.
The problem is that in general, algorithms are not specified in perfect detail, or they are implemented in ways that are logicially equivalent, but not exactly equivalent, with the specification. (Or oftentimes both). When dealing with any specific algorithm, we can usually infer that analyses of one will translate to the other, but in the general case, this assumption is murky.
The difference between functional and non-functional for an algorithm happens at the level of the specification, which is different from the level of the implementation. The translation from one to the other involves optimization. And if perfect optimization is undecidable, as you point out, so is the question of whether a perfectly optimized implementation of one class of algorithms is 'better' than a perfectly optimized implementation of another class, since we're no longer dealing with individual instances.
In the general case, not necessarily for any subset, and this would apply to to non-functional algorithms as well. Just because I write a 'simple' for/while loop, that doesn't necessarily imply anything about the actual
At the end of the day, an algorithm is simply an unambiguous, executable, and terminating specification of a way to solve a problem. We may implement an algorithm by creating a physical or virtual machine that conforms to that specification, but even abstractions like Turing machines and lambda calculi are just attempts at creating a deterministic model that we can manipulate in order to understand the algorithm, which is an abstract specification.
The problem is that in general, algorithms are not specified in perfect detail, or they are implemented in ways that are logicially equivalent, but not exactly equivalent, with the specification. (Or oftentimes both). When dealing with any specific algorithm, we can usually infer that analyses of one will translate to the other, but in the general case, this assumption is murky.
The difference between functional and non-functional for an algorithm happens at the level of the specification, which is different from the level of the implementation. The translation from one to the other involves optimization. And if perfect optimization is undecidable, as you point out, so is the question of whether a perfectly optimized implementation of one class of algorithms is 'better' than a perfectly optimized implementation of another class, since we're no longer dealing with individual instances.