My point is that focusing on the halting theorem is silly, because we have much more precise and less binary generalisations of it since 1965. Finding "practical approximations" that are easier than the hard limits is not only not easy, but a huge deal.
> The sequences "converge to" or "approximate increasingly well" the true halting function in that for any input, there is some point in the sequence such that all subsequent partial halting oracles analyze its behavior correctly.
This is irrelevant. It is obviously the case that a "there exists X such that for all Y" is very different from "for all Y there exists X", yet the latter is by no means an "effective approximation" of the former.
At the end of the day, we're always looking for some algorithm that is useful for a large class of inputs, and we know that any such algorithm cannot violate the time hierarchy in any way. It will be able to efficiently solve problems that are easy and unable to efficiently solve problems that are hard. Having any algorithm solve more problems will require it to run longer.
It may be the case that a large set of practical problems are easy, but it is also the case that a large set of practical problems are hard. Only a world-changing discovery such that P = PSPACE or that there are tractable and useful approximations for all of PSPACE will change that.
That doesn't mean, of course, that there may be many interesting easy problems that we're yet to solve.
> This is irrelevant. It is obviously the case that a "there exists X such that for all Y" is very different from "for all Y there exists X", yet the latter is by no means an "effective approximation" of the former.
If there's an algorithm that gives the correct answer to the halting problem for "lots of inputs," I think that's very relevant - particularly if we can get a sequence of such algorithms that get closer and closer to the behavior of a true halting oracle!
> At the end of the day, we're always looking for some algorithm that is useful for a large class of inputs, and we know that any such algorithm cannot violate the time hierarchy in any way. It will be able to efficiently solve problems that are easy and unable to efficiently solve problems that are hard. Having any algorithm solve more problems will require it to run longer.
I don't think it's clear that a time hierarchy even exists for randomized Turing machines, but even if it does, this is again only true in an asymptotic sense...
> It may be the case that a large set of practical problems are easy, but it is also the case that a large set of practical problems are hard. Only a world-changing discovery such that P = PSPACE or that there are tractable and useful approximations for all of PSPACE will change that.
Figuring out if an algorithm is in P/PSPACE/etc to begin with is much harder than solving the halting problem!
> The sequences "converge to" or "approximate increasingly well" the true halting function in that for any input, there is some point in the sequence such that all subsequent partial halting oracles analyze its behavior correctly.
This is irrelevant. It is obviously the case that a "there exists X such that for all Y" is very different from "for all Y there exists X", yet the latter is by no means an "effective approximation" of the former.
At the end of the day, we're always looking for some algorithm that is useful for a large class of inputs, and we know that any such algorithm cannot violate the time hierarchy in any way. It will be able to efficiently solve problems that are easy and unable to efficiently solve problems that are hard. Having any algorithm solve more problems will require it to run longer.
It may be the case that a large set of practical problems are easy, but it is also the case that a large set of practical problems are hard. Only a world-changing discovery such that P = PSPACE or that there are tractable and useful approximations for all of PSPACE will change that.
That doesn't mean, of course, that there may be many interesting easy problems that we're yet to solve.