> 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!
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!