[FOM] Absolute undecidability

[Timothy Y. Chow]

Arne Hole wrote:

> We say that an infinite bit sequence {b_n} is a TAIL of the infinite bit 
> sequence {a_n} if there a natural number k such that b_n=a_(n+k)  for 
> all natural numbers n. Then we may say that a property P of infinite bit 
> sequences definable in L(PA) is NONTRIVIAL (wrt to an infinite number of 
> bits) iff it has the following properties:
>
> (i) If {a_n} has the property P , then all tails of {a_n} also have the 
> property P
>
> (ii) The probability that an infinite p = 0.5 Bernoulli sequence has the 
> property P, is less than 1.

This is precise, but I wonder how plausible it is that we cannot obtain 
nontrivial knowledge in this sense.

There are a number of conjectures that hypothesize that some object that 
we understand rather poorly behaves "randomly."  For example, it is 
commonly conjectured that various irrational numbers are normal in every 
base, and there are various heuristic techniques in number theory that 
pretend that the prime numbers are random.  Although these conjectures are 
plausible, they can sometimes go wrong.  There is a nice list on 
MathOverflow of examples where a randomness heuristic fails:

http://mathoverflow.net/questions/11978/heuristically-false-conjectures

Regarding bit-expansions of numbers, it is perhaps not so well known to 
non-number theorists that some things can be said about infinitely many 
as-yet-uncomputed bits of (say) pi.  The irrationality measure of pi is 
known to be less than 8.  This in particular implies that for all 
sufficiently large n, the nth through the (8n)th bits of pi cannot all be 
zero.  Of course, this is a very weak statement about the bits of pi, and 
I don't think it can be turned into nontrivial information in your sense. 
Still, examples of this sort make me a bit cautious about hypothesizing 
that it is impossible to obtain nontrivial information in your sense.

Tim