When I define a probabilistic Turing machine I give it a special "coin state" which it enters and magically lands in a special "heads" state and "tails" state uniformly and independently each time. I imagine a computer hooked up to a little box with a coin inside that gets flipped and some sensor or camera determines whether it landed heads or tails.
I have no problems thinking about probabilistic computation just like I have no issues with quantum machines which haven't been built yet or nondeterministic machines which will never exist.
We don't care where those random bits come from as long as they fulfill the right properties. Of course our computers don't have little coin boxes so they generate randomness using pseudorandom generators which don't fulfill all the properties we expect from true randomness. So we developed theories of PRGs and under what assumptions good PRGs exist. Whether we can use them depends on whether we use randomness for searching or hiding.
We can't disprove that BPP = NEXP (everything in nondeterministic exponential time can be solved in probabilistic polynomial time). Then true randomness will give us the secrets of the universe and PRGs won't help much. Random bits would be worth their weight in gold but can we get them? I'd make a fortune selling little coin boxes.
Information that we are willing to bet on.
ReplyDeleteDo you mean "unwilling to bet on"?
Linux (as least) maintains an "entropy pool", tossing in random bits from the timing of external events deemed to be random, and hands this out via /dev/random, I think. The entropy only grows at somewhat slow rate, so you can do a "entropy denial-of-service" by continually reading as much as you can. This can be combined with pseudo-random generators to avoid the denial-of-service, but then you lose unpredictability.
ReplyDelete> Random bits would be worth their weight in gold but can we get them?
ReplyDeleteYes. Stick a photon into a beamsplitter.
http://www.idquantique.com/true-random-number-generator/products-overview.html
To mathematicians, “random” is associated to processes that spin gold into straw (e.g. deterministic seeds into random-looking strings, plaintext into ciphertext, disequilibrium into equilibrium). To engineers, “random” is associated to time-reversed processes that spin straw into gold (e.g. ciphertext into plaintext, quantum errors into quantum coherence, dilute solutions into concentrated solutions).
ReplyDeleteThat so many randomized processes have a physically and/or mathematically and/or and informatically natural time-reversed dual is a great Hakuna Matata of the 21st century STEM enterprise. :)
Assuming standard Quantum Mechanics, we CAN get random bits (for example by a 2-slit experiment, detecting particles on the other side. The probability of each particle taking the upper path is 1/2. Small discrepancies in building the apparatus do not matter because BPP with "almost perfect coins" = BPP.)
ReplyDeleteI am not claiming that building such devices is practical, just that it would totally upset most of Physics if one assumed that true randomness did not exist in nature.
I attempted an "exploration" of randomness in the post on this site:
ReplyDeletehttp://www.tarotforum.net/showthread.php?t=140495
CSProf: As Matt Leifer pointed out, using QM for randomness generation is perfectly practical! You can buy a device that does it right now.
ReplyDelete