= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on Attempts to work around Goedel's theorem by using randomness - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (17)
The outlined approach wouldn't contradict Goedel's theorem if it worked. (The ideal outcome would be a randomized method for generating axiom systems that have a high probability of being "true" over the standard integers and a high probability of resolving some concrete math question. Goedel's theorem doesn't prohibit that.) I'm going to interpret your comment charitably, as saying you already understand that, but you think there's some general law of nature that adding randomness can never help. That's not always true, I think.
What was the reconciliation between that principle and the optimal solution on Absent-Minded Driver?
Here's an example that's similar to AMD in this respect, but a lot simpler. We make two copies of you and ask each to output a bit. If the bits are different, you win a million dollars, otherwise nothing. Any deterministic algorithm loses, but a randomized one can win with probability 50%. Does it overthrow Eliezer's principle? What exactly is Eliezer's principle? I don't know :-)
I wasn't trying to criticize it -- I think it's a great heuristic and I think it touches on a very fundamental, non-obvious aspect of reality. I just want to better understand what kind of exception AMD and your game are.
For example, in cases where you don't want to "improve" something for someone, randomness is, in a sense, good. For example, when hiding messages from an adversary, adding randomness is good -- though only because it's bad for someone else. This is consistent with the anti-randomness heuristic.
I phrased it one time as, "Randomness is like poison: yes, it can help you, but only if someone else takes it."
It seems like there's some word-trickery going on here. A randomized algorithm is just a deterministic algorithm plus a source of randomness, but the randomness source isn't counted as an "input" but instead "part of the algorithm". AMD is a situation where you want two copies of the same algorithm with the same inputs to have a different output, which is impossible. Using a "randomized" algorithm allows you to sneak around this limitation by giving each copy a possibly different input without calling it an input.
Good point, but how is that a case of word-trickery, and what would you call this category of exception to the anti-randomness heuristic?
Here's an old comment thread where I tried to explain how I think about this.
The short version is this: Adding randomness is only useful when you are trying to obfuscate. Otherwise, adding randomness per se is always bad or neutral. However, many cases that are described as "adding randomness" are really about adding some information that turns out to be just what the agent needs, plus some randomness that turns out not to do any harm.
For example, in the AMD problem, the optimal strategy is often described as "exit with probability 1/3rd". Now, what this really means is the following: The agent is given an input channel C, together with the knowledge that the input from C will belong to a set S such that some known set T contains 1/3rd of the elements of S (but no additional information). The agent then implements the deterministic algorithm of exiting iff the input from C belongs to the set T.
People often explain why this agent is able to do better than an agent without a "mixed" strategy by saying, "This agent has a source of randomness." But I think that it's better to say that the agent has an input channel about which it knows something, but not everything. In contrast, the agent employing a "non-mixed" strategy doesn't have this information about the channel. So, naturally, the agent with the "mixed" strategy does better, because it knows more.
Thanks. I had forgotten that a clearer resolution of those heuristics had eventually been offered as that thread developed, and I appreciate you summarizing it here.
For onlookers: also see this old thread, especially Scott Aaronson's comments.
See my comments there too: I think that's the only time I'll ever outwit Aaronson on computer science (if only because he kept cheating by chaning the question).
Edit: Okay, that may be overstating; let's just say that's the best I'll probably ever do against him on comp-sci.