| > Did you know that the naturals are a subset of the reals? Well, all I can say here is that my intuition suggested to me that proofs about the complexity of a set are generally not extensible to much-less-complex subsets. But OK. If you want an objection stated in terms of Richardson's theorem, where are we invoking the sine function? > Irrespective of where you're convinced it's 100% true that equality of two functions is undecidable in general. So what? We're not trying to decide the equality of two functions in general. We're deciding the equality of two functions in specific. > If Richardson's doesn't convince you there's also https://en.m.wikipedia.org/wiki/Rice%27s_theorem >> Is P equivalent to a given program Q? Again, why is this supposed to matter? Here are two programs in C: int main(int argc, char* argv[]) {
return 0;
}
int main(int argc, char* argv[]) {
return 3 + 1 - 4;
}
Is it undecidable whether those two programs are equivalent?Rice's theorem says there is no algorithm which will take two programs as input and return yes if they're equivalent while returning no if they aren't. But no attempt has been made to supply such an algorithm. |