There's a problem: Kleene's O in its full generality goes beyond any computable theory, because any such theory has a limit computable ordinal which is not provably well ordered. Your question sounds like a strong statement of Cohen's "article of faith" from "Set Theory and the Continuum Hypothesis" that any arithmetic question is resolved by a large enough axiom of infinity (if it is understood that any large axiom of infinity is equivalent to the well-foundedness of a recursive ordinal). So how can your statement be proven? Even replacing "hyperarithmetic" by "pi-0-1" (halting problem)?

This is a truly great answer. But you use"Newton series" and "superfunction" in a way that will be misleading. By the "Newton series" you mean expansion of (1+x)^(1/2) in powers of x, not "Newton's iteration method", which is how some people read it. By "Superfunction" you mean an abstract iteration operator which when applied to functions composes them with other functions. This formula is a little hard to make precise.

You can find the answer to the trapping questions numerically by simulating an infinite non-trapping walk, and looking at the probability cost of enforcing no-trapping at each time-step (I did this recreationally once, for the getting the asymptotic number of self-avoiding walks of length n-- it gives the wrong answer). Maybe you can get a different universality class for random paths which are allowed to collide, but not cross. It is possible that this condition makes sense, even if the original question is not the right one.

You should ask the question for the lattice version only--- the Brownian version can't trap itself.

Perhaps this should be a question: is the maximal extension of Chonquet Bruhat always separable? The answer I give says no, but I am doubting now.

Since this got downvoted, I started to worry that it might be incorrect. In particular, if one considers only regions which are a bounded geodesic distance from a given point, can the tree have infinitely many branchings? But it can, because the scale invariance allows ever smaller maximally extended black holes along a finite length geodesic to accumulate with nothing going wrong at the accumulation point.

Rather than say "flaw", as if the proof is inherently wrong, you can ask "can you spot where choice ruins this probablistic argument?". Proofs like these are perfectly OK in a Solovay universe, and probability working correctly can be argued to be vastly more important than ineffable Hamel bases/well-orderings.

@Chow-- Thank you for stating it so clearly. I wanted to also emphasize that this is really the only counterintuitive aspect of uncountable choice, all the other examples are special cases. For example, the "predict the future/hats" business is counterintuitive because our intuition suggests that we can choose an infinite sequence of future-events/hat-colors at random. The axiom of choice forbids us from choosing at random. We must choose in an L-like model where choice holds. Similarly, random picks forbid Hamel bases for R over Q and for well-ordering of R, so this is the serious conflict.

It is traditional to say loosely of the adjoined random real "r" that it is a member of the set of irrational numbers, even though of course it is not a member of the old model's irrational numbers. The whole point of forcing is that it gives you a way to settle every question of the form "does r belong to S" in a way that is correct for random objects. Without doing this, you have not really defined a random object completely. So before Solovay, no one had really defined randomness satisfactorily (although of course Cohen had given the main idea).

If you have a sequence of independent 0-1 events which are in every way identical, then any permutation of the 0s and 1s is just as likely to occur as any other. In order for the limit not to exist, there must be long segregated 0's followed by segregated 1's. But any segregated sequence of length N is segregated in only a negligible fraction of all permutations of this sequence, and the 0s and 1s can come in any permutation. There is no way in the world that an independent sequence of identical probabilistic 0-1's can fail to converge.

This answer is incorrect. If you formalize the notion of random picking, the result is random reals a la Solovay, and these require all subsets of R to be Lebesgue measurable, precisely because it is impossible for a sequence of random independent 0-1 events to oscillate in the way you describe. This follows from the permutation invariance of independent random events.

Thank you for explaining this constructive measure theory business. Although your answer is self-contained, I was wondering if you can add a literature pointer, just for my own edification. For the specific questions: I didn't think about topology on the space of distributions, because Solovay guarantees that the measure will be defined on all subsets without worrying about topology. But, as you pointed out, there is the implicit topology in the statement that the random-picking algorithm converges. This allows you to easily make a countable dense set in the support.