4 ms·
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 ha
by 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 agoMy 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.