Wadge Hardness and Randomness

BECHER, VERÓNICA; GRIGOREFF, SERGE

Wadern, Germany

Workshop; Seminar on Topological and Game Theoretic Aspects of infinite computations, Schloss Dagstuhl, Wadern, Germany, June to 4 July 2008.; 2008

Schloss Dagstuhl

We obtain a large class of significant examples of $n$-random reals. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite inputs produces an output in a given set $O$. The input space is the Cantor space $2^omega$. The output space is the space of equivalent classes of limits of nondecreasing sequences of elements in a given a countable set endowed with a computable order. For instance, $2^{leq omega}, R, Q, P(N), C[0,1]$. We give a general theorem that, roughly, it says "the harder the set $O$, the more random the associated probability". The proof uses effective Wadge reductions from $Sigma^0_n$ (or $Pi^0_n$) classes in the Cantor space. In particular, we develop methods to transfer $Sigma^0_n$or $Pi^0_n$ many-one completeness results of index sets to $n$-randomness of associated probabilities