Algorithmic probability problems

Reading topics - Feb 2024

Sum operator

Definition. We say that a rational sequence (ai) is {} if it is computable, ai < ∑j > iaj and j > iaj is a computable real  < 1.

We fix admissible (ai) and let A[X] := ∑i ∈ Xai.


Question. Is it true that:

Question. Is it true that:

About random left c.e. reals

Definition. Let s be the Solovay reducibility on the left c.e. reals and

For left c.e. reals, α<sγ iff there exists rational c > 0 and left c.e. β with c ⋅ γ = α + β.

Exercise. Show that there are ∅′-left c.e. reals α, γ such that α is random, β is not random and αs1γ?

Remark 1. This says that 1-randomness is not upward s1-closed in the ∅′-left c.e. reals. In contrast, 2-randomness is upward s1-closed in the ∅′-left c.e. reals.

Hint. You need to produce ∅′-left c.e. α, γ which are not ∅′-random, and although α is less compressible than γ, relative to oracle ∅′ it is more compressible than γ. For example, α = Ω and γ = Ω∅′ ⊕ ∅. Here you need to use the fact that if αK1γ then αs1γ; this is a relativization of a known fact due to Stephan.

Remark 2. By the hint above, there exists βT∅′ such that Ω + β is not random. By the result in `differences of halting probabilities’, this β can be chosen to be random and a d.c.e. real (the difference of two left c.e. reals). So the sum of two (positive) random reals may not be random. In this case, it is necessary that one of them is left c.e. and the other is a real. For each random left c.e. α there exists random β such that α − β is not random.

Question. Is it true that for each nonrandom left c.e. real α there exists:

The question if, given left c.e. α there exists left c.e. β with α + β having a certain property is the same as asking if there exists left c.e. γsα with the said property.

So we ask if for each nonrandom left c.e. real α there exists:

Push game

Two players produce an increasing sequence rs by adding increases in turn. Player 2 wins if r := limsrs is outside a given open set V. The increases available to Player 1 are chosen (without repetition) from the terms of a given admissible (ai) (many ai can be chosen at once). Similarly for Player 2 with respect to admissible (bi).

Formally, given an effectively open set V with μ(V) = 1/2 and admissible sequences (ai), (bi), two players pick sets F0, G0, F1, G1, … in turns, so that

Player 2 wins if there exists increasing (ts) with sr2s ∉ Vts. Who wins?