[math-fun] preprint: uncertainty principle in AIT
Greg Chaitin defined Omega_U as the halting probability for a self-delimiting Turing machine U. (Self-delimiting means that the domain of U is a prefix-free set; that is, no program is the prefix of another.) I noticed that Chaitin's theorem about the (un)computability of bits of Omega_U can be recast as an uncertainty principle. My professor and I have written a paper; a preprint is available at http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf I'd appreciate any comments. Thanks! -- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
Interesting paper. Thanks for the note. David H Bailey -----Original Message----- Greg Chaitin defined Omega_U as the halting probability for a self-delimiting Turing machine U. (Self-delimiting means that the domain of U is a prefix-free set; that is, no program is the prefix of another.) I noticed that Chaitin's theorem about the (un)computability of bits of Omega_U can be recast as an uncertainty principle. My professor and I have written a paper; a preprint is available at http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf I'd appreciate any comments. Thanks!
I failed to find in the paper any connection between Godel's incompleteness and randomness in physics, other than a stated conjecture that such exists. I see no application of Godel incompleteness to physics. Questions such as whether the whole of physics is finitely describable are unanswerable, since, unlike mathematics, physics is limited by what can be measured rather than by what can be postulated. But here is something to contemplate. A polarizing beam splitter is a device that splits an input light beam into its horizontally and vertically polarized components, and both of these beams are output. Unlike Polaroid sheet, there is no absorption. If the input light is linearly polarized at 45 degrees, the output beams have equal power. Measure each output beam with a detector that can detect individual photons. For each horizontally polarized photon, output a zero; for each vertically polarized photon, output a one. Now you have a random bit stream. Because of alignment and material imperfections, the probability of 0 and 1 cannot be made precisely 1/2. Computer scientists expend a tremendous effort trying to design computational pseudorandom number generators. But through quantum mechanics, you get it for free as a gift from nature. Gene --- Mike Stay <staym@clear.net.nz> wrote:
Greg Chaitin defined Omega_U as the halting probability for a self-delimiting Turing machine U. (Self-delimiting means that the domain of U is a prefix-free set; that is, no program is the prefix of another.) I noticed that Chaitin's theorem about the (un)computability of bits of Omega_U can be recast as an uncertainty principle. My professor and I have written a paper; a preprint is available at
http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf
I'd appreciate any comments.
Thanks!
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
__________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools
Boris Alexeev found the following, as a part of a little contest suggested by Erich Friedman. 2004 = ceil( (6 - sqrt6)^6 ) --Ed Pegg Jr-- www.mathpuzzle.com www.maa.org
ed
Boris Alexeev found the following, as a part of a little contest suggested by Erich Friedman.
2004 = ceil( (6 - sqrt6)^6 )
way cool! i never use sqrt or ceil in puzzles like this, but this is incredibly surprising! erich
On Monday, February 23, 2004, at 01:10 PM, Eugene Salamin wrote:
Measure each output beam with a detector that can detect individual photons. For each horizontally polarized photon, output a zero; for each vertically polarized photon, output a one. Now you have a random bit stream.
These exist as devices to plug into your USB port. Um, here's one: http://www.gapoptic.unige.ch/Prototypes/QRNG/ I wonder whether that's easier than using radioactive decay, the other obvious way that the laws of quantum mechanics give us genuine randomness?
Because of alignment and material imperfections, the probability of 0 and 1 cannot be made precisely 1/2.
There are lots of ways to make "almost random" streams better. If you really have independent, identially distributed Bernoulli trials and the only worry is that p=1/2+epsilon, the easiest remedy is Von Neumann's: look at generated bits two at a time, and apply "10" -> 0 "01" -> 1 throw away "11" and "00". This cuts your output rate in half (-2epsilon^2), but if there's really no short-term correlation, you get true randomness. --Michael Kleber kleber@brandeis.edu
Date: Mon, 23 Feb 2004 13:30:11 -0500 From: Michael Kleber <kleber@brandeis.edu> "10" -> 0 "01" -> 1 throw away "11" and "00". This cuts your output rate in half (-2epsilon^2), but if there's really no short-term correlation, you get true randomness. That actually cuts your output rate by a factor of 4, not 2, right? If 2 input bits always gave you an output bit, that would cut the rate in half. But 2 input bits gives you an output bit only half the time, so it's a factor of 4. Andy
Oof. Yes, of course, you're right... --Michael On Monday, February 23, 2004, at 03:37 PM, Andy Latto wrote:
Date: Mon, 23 Feb 2004 13:30:11 -0500 From: Michael Kleber <kleber@brandeis.edu>
"10" -> 0 "01" -> 1 throw away "11" and "00".
This cuts your output rate in half (-2epsilon^2), but if there's really no short-term correlation, you get true randomness.
That actually cuts your output rate by a factor of 4, not 2, right? If 2 input bits always gave you an output bit, that would cut the rate in half. But 2 input bits gives you an output bit only half the time, so it's a factor of 4.
Perhaps a simpler way to get a truly random bit stream is to amplify and digitize the inherent random electrical noise produced by a resistor at a nonzero temperature. This is not a new idea, obviously, and is probably used in some practical applications. Steve Gray ----- Original Message ----- From: "Eugene Salamin" <gene_salamin@yahoo.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Monday, February 23, 2004 10:10 AM Subject: Re: [math-fun] preprint: uncertainty principle in AIT
I failed to find in the paper any connection between Godel's incompleteness and randomness in physics, other than a stated conjecture that such exists.
I see no application of Godel incompleteness to physics. Questions such as whether the whole of physics is finitely describable are unanswerable, since, unlike mathematics, physics is limited by what can be measured rather than by what can be postulated.
But here is something to contemplate. A polarizing beam splitter is a device that splits an input light beam into its horizontally and vertically polarized components, and both of these beams are output. Unlike Polaroid sheet, there is no absorption. If the input light is linearly polarized at 45 degrees, the output beams have equal power. Measure each output beam with a detector that can detect individual photons. For each horizontally polarized photon, output a zero; for each vertically polarized photon, output a one. Now you have a random bit stream. Because of alignment and material imperfections, the probability of 0 and 1 cannot be made precisely 1/2. Computer scientists expend a tremendous effort trying to design computational pseudorandom number generators. But through quantum mechanics, you get it for free as a gift from nature.
Gene
--- Mike Stay <staym@clear.net.nz> wrote:
Greg Chaitin defined Omega_U as the halting probability for a self-delimiting Turing machine U. (Self-delimiting means that the domain of U is a prefix-free set; that is, no program is the prefix of another.) I noticed that Chaitin's theorem about the (un)computability of bits of Omega_U can be recast as an uncertainty principle. My professor and I have written a paper; a preprint is available at
http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf
I'd appreciate any comments.
Thanks!
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
__________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Monday, February 23, 2004, at 01:44 PM, Steve Gray wrote:
Perhaps a simpler way to get a truly random bit stream is to amplify and digitize the inherent random electrical noise produced by a resistor at a nonzero temperature. This is not a new idea, obviously, and is probably used in some practical applications.
The Intel hardware RNG is built in part on this. There's a good white paper at http://www.intel.com/design/security/rng/CRIwp.pdf But using quantum physics is so much sexier... --Michael Kleber kleber@brandeis.edu
--- Michael Kleber <kleber@brandeis.edu> wrote:
The Intel hardware RNG is built in part on this. There's a good white paper at http://www.intel.com/design/security/rng/CRIwp.pdf
But using quantum physics is so much sexier...
--Michael Kleber kleber@brandeis.edu
Does Intel explain how to use their random number generator? Can I do something like: #define RANDOM 0xFEDCBA98 // internal register int MyRandomNumber; MyRandomNumber = *((int *)RANDOM); Gene __________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools
On Monday, February 23, 2004, at 02:09 PM, Eugene Salamin wrote:
Does Intel explain how to use their random number generator? Can I do something like:
#define RANDOM 0xFEDCBA98 // internal register int MyRandomNumber; MyRandomNumber = *((int *)RANDOM);
It's (only a little) more involved than that -- you need to check that a new random byte is available before you read it each time, for example. Their web site has pseudocode and links to an API to access it, though. Check out http://developer.intel.com/design/security/rng/rngres.htm and related pages. --Michael Kleber kleber@brandeis.edu
From the Intel page, this is apparently already part of each Pentium. I don't know if the latest Pentia have this capability or not. http://www.intel.com/design/security/rng/rnghow.htm "The Intel Random Number Generator was designed in accordance with two critical design criteria: * The RNG must be based on a source that's truly random and based on properties native to silicon circuitry. * The design must preserve this randomness while providing the needed performance and circuit stability across temperature and other environmental effects. To meet these criteria and others, the Intel RNG uses white noise as the random source, then processes the data through a variety of circuit elements. Intel RNG is available in Intel® chipsets, beginning with the Intel® 810 Chipset for the Intel® Celeron_ processor. This capability is also planned for the next-generation Intel® 8xx chipset for the Pentium® III processor." At 10:44 AM 2/23/2004, Steve Gray wrote:
Perhaps a simpler way to get a truly random bit stream is to amplify and digitize the inherent random electrical noise produced by a resistor at a nonzero temperature. This is not a new idea, obviously, and is probably used in some practical applications.
Steve Gray
----- Original Message ----- From: "Eugene Salamin" <gene_salamin@yahoo.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Monday, February 23, 2004 10:10 AM Subject: Re: [math-fun] preprint: uncertainty principle in AIT
I failed to find in the paper any connection between Godel's incompleteness and randomness in physics, other than a stated conjecture that such exists.
I see no application of Godel incompleteness to physics. Questions such as whether the whole of physics is finitely describable are unanswerable, since, unlike mathematics, physics is limited by what can be measured rather than by what can be postulated.
But here is something to contemplate. A polarizing beam splitter is a device that splits an input light beam into its horizontally and vertically polarized components, and both of these beams are output. Unlike Polaroid sheet, there is no absorption. If the input light is linearly polarized at 45 degrees, the output beams have equal power. Measure each output beam with a detector that can detect individual photons. For each horizontally polarized photon, output a zero; for each vertically polarized photon, output a one. Now you have a random bit stream. Because of alignment and material imperfections, the probability of 0 and 1 cannot be made precisely 1/2. Computer scientists expend a tremendous effort trying to design computational pseudorandom number generators. But through quantum mechanics, you get it for free as a gift from nature.
Gene
--- Mike Stay <staym@clear.net.nz> wrote:
Greg Chaitin defined Omega_U as the halting probability for a self-delimiting Turing machine U. (Self-delimiting means that the domain of U is a prefix-free set; that is, no program is the prefix of another.) I noticed that Chaitin's theorem about the (un)computability of bits of Omega_U can be recast as an uncertainty principle. My professor and I have written a paper; a preprint is available at
http://www.cs.auckland.ac.nz/CDMTCS/researchreports/235cris.pdf
I'd appreciate any comments.
Thanks!
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
And of course there's the venerable http://www.fourmilab.ch/hotbits/ Getting back to the arguments between uncertainty in physics and undecidability in mathematics (assuming this topic is also FUN): To differ a bit: I also used to readily discount this alleged connection as mystical, but lately I'm more sympathetic to a further dialog. Don't we only believe these hardware generators to be "truly" random to the extent that we believe that the empirical evidence supports the theory that says they "truly" are? And, how is an experimental outcome being "truly" unpredictable, given all physical observables and applicable laws, different, in principle, from a theorem being "truly" undecidable, given all axiomatic derivables? A possible (and now conventional) model of reality essentially consists of a Platonic universe in which axiomatic inevitables reside (such as the mathematical laws of physics) plus this bizarre additional inscrutable mechanism that arbitrarily squirts out "truly" random bits that then determine (via the laws) all the otherwise theoretically-uncertain physically observed actualities. But it would seem another possible model is that there is only the one kind of universe, and this supposedly "truly" random extra component is merely akin to the inevitable additional "sporadic facts" that we know must appear in any derivational system. Until the relationship between these apparently different models is satisfactorily clarified (say by showing them either equivalent or experimentally differentiable) there will remain an uneasy urge to shave off that protruding random bit spigot with Occam's razor. So I feel that in its introductory motivation the paper may implicitly exaggerate the plausibility of the random-spigot-free model of reality somewhat, but the result about the structural similarity of the Platonic and physical uncertainty laws is independently interesting and, to my limited understanding, at minimum contributes something to this dialog.
participants (10)
-
Andy Latto -
David H Bailey -
Ed Pegg Jr -
Erich Friedman -
Eugene Salamin -
Henry Baker -
Marc LeBrun -
Michael Kleber -
Mike Stay -
Steve Gray