5 ms·

I think Eliezer is failing to consider a very important set of problems--those for which the set of dumb things to do is small, but delimiting that set is extre

I think Eliezer is failing to consider a very important set of problems--those for which the set of dumb things to do is small, but delimiting that set is extremely difficult. An example given in another comment is Monte Carlo integration: you know that the set of points at which the function is ill-behaved is small, and that you want to avoid these points, but it is computationally unfeasible to determine which points they are. These examples abound in mathematics, where it is often easy to show that the set of "trouble points" in some generalized sense is small, but very hard to determine where these points are. In a more technical sense, whether randomness gives algorithms more power is still an open question in computer science (depending on interpretation, the question is either whether RP=P or whether BPP=P). The answer is widely believed to be that it does not, but this is on the basis of the hypothesized existence of strong psuedorandom algorithms rather than randomness being useless.

Verdex 12y ago
As far as your first point is concerned, it has been 6 years since Eliezer first wrote that post so I wonder if maybe he would give a more nuanced view if he had to write it again. Perhaps to include the twice mentioned Monte Carlo integration. Your second point is something I hadn't really thought about. If I understand you correctly, you're saying that Eliezer is probably correct, but it doesn't matter because randomness is an incredibly useful tool that we would use regardless of whether or not RP = P or BPP = P. I'm interested if you (or really anyone) could expound on that a bit? I guess the analogue that comes to mind is that I find monads to be a really easy way to write parsers and it's really lucky for us that bind happens to be derivable from the monadic laws, but I'm not doing anything that can't be done on a turing machine. Is that more or less on track?
- alexbecker 12y ago
  My point that probably P=RP=BPP is that randomness probably doesn't give you any computational power, but not for the reason Eliezer gives (that we can come up with an equally good structured way to do things), but rather because we can make deterministic algorithms which look sufficiently like they're using randomness. I don't think your analogy really holds up--monads are just an abstraction implemented on a turing machine, they can't possibly give you anything a turing machine can't, since you are actually using a turing machine. With randomness you are in principal actually extending a turing machine, although it's an open question whether or not this actually gains you anything.

Verdex 12y ago

As far as your first point is concerned, it has been 6 years since Eliezer first wrote that post so I wonder if maybe he would give a more nuanced view if he had to write it again. Perhaps to include the twice mentioned Monte Carlo integration. Your second point is something I hadn't really thought about. If I understand you correctly, you're saying that Eliezer is probably correct, but it doesn't matter because randomness is an incredibly useful tool that we would use regardless of whether or not RP = P or BPP = P. I'm interested if you (or really anyone) could expound on that a bit? I guess the analogue that comes to mind is that I find monads to be a really easy way to write parsers and it's really lucky for us that bind happens to be derivable from the monadic laws, but I'm not doing anything that can't be done on a turing machine. Is that more or less on track?

alexbecker 12y ago
My point that probably P=RP=BPP is that randomness probably doesn't give you any computational power, but not for the reason Eliezer gives (that we can come up with an equally good structured way to do things), but rather because we can make deterministic algorithms which look sufficiently like they're using randomness. I don't think your analogy really holds up--monads are just an abstraction implemented on a turing machine, they can't possibly give you anything a turing machine can't, since you are actually using a turing machine. With randomness you are in principal actually extending a turing machine, although it's an open question whether or not this actually gains you anything.