(Comments inline) Eugene Salamin wrote:
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.
Well, the abstract does say that we're *not* looking at incompleteness implying randomness in physics. What we showed was that uncertainty--formally equivalent to Heisenberg's relation in all cases and physically equivalent in some particular cases--implies incompleteness. Perhaps we need to emphasize that more? The conjecture was made by my professor's friend (and I'm sure it has been made before); the only thing our paper contributes toward that conjecture is another hint that some kind of relationship between them seems to exist. Do you think we should strike the conjecture? It was really tacked on at the end.
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.
I agree. One interesting paper I read claimed to show that if your physical theory predicts that some measureable quantity is equal to an uncomputable number, you'll never be able to verify your theory algorithmically! Of course, if the Church-Turing thesis is false for some physical system, then perhaps we could use that to verify it.
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
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039