FOM: Probabilistic proofs, a question:

Soren Moller Riis smriis at
Tue Sep 22 14:01:19 EDT 1998

Probabilistic proofs, a question:

Suppose we flip a couple of thousand coins and
generate a binary string "randomly". 
Suppose we can prove in ZFC that IF this string 
is not compressible (to say half its length), THEN 
the Riemann Conjecture is valid.

How should we react to this?? Perhaps nature
follows some completely recursive principles
with very low Kolmogorov complexity. Perhaps 
it is physical IMPOSSIBLE to produce ANY Kolmogorov 
random string beyond a certain length. 

Thus it seems to me that mathematical deductions 
derived from assuming that a physically generated 
"random" string not is Kolmogorov random, must
be rather controversial.

Here is a theoretical question: 

The the set of numbers which are Kolmogorov random 
is clearly a non-recursive simple set. Does this set has
any completeness properties?

If for example it was one-to-one complete (which I suppose
must be impossible) we could reduce (in a recursive
fashion) any instance of the halting problem to whether
a specific number is Kolmogorov random.

Especially both the Riemann Conjecture, as well as the
Poincare Conjecture (which each are equivalent to a 
universal sentence (according to J. Shipman)) can be 
reduced to whether specific strings are random
(in Kolmogorovs sense)  or not.

Question: What kind of reductions (if any) do we have
from ordinary r.e. decision problems, to the set of
Kolmogorov random numbers?

Soren Riis

More information about the FOM mailing list