ファイル置き場 Sendai Logic Homepage 100514peng

(1)

Algorithmic Randomness and Lowness Notions

NingNing Peng

Mathematical Institute, Tohoku University, Sendai 980-8578, Japan [email protected]

May 14, 2010

NingNing Peng Algorithmic Randomness and Lowness Notions

(2)

1 Randomness and Kolmogorov Complexity Complexity & Randomness

Some theorems

2 Main Result: X-Randomness X-Randomness

Facts about X-random sets Future research

3 Lowness properties and Randomness Three lowness properties

Proof (iV) of Main theorem

(3)

The Cantor Space

2^ω is the space of infinite binary strings: the reals

(4)

The Cantor Space

2^ω is the space of infinite binary strings: the reals 2^<ω is the space of finite binary strings.

(5)

The Cantor Space

The standard topology on 2^ω is induced by the basic open sets: [σ] ={σX : X ∈ 2^ω} for all σ ∈ 2^<ω.

(6)

The Cantor Space

Lebesgue measure on the Cantor space: the measure of a basic open set [σ] is λ([σ]) = 2^−|σ|.

(7)

The Cantor Space

Lebesgue measure on the Cantor space: the measure of a basic open set [σ] is λ([σ]) = 2^−|σ|.

(8)

Selective history of Kolmogorov Complexity

Solomonoff (1964) and Kolmogorov (1965) independently definedKolmogorov complexity, measuring the information content of finite strings.

(9)

Selective history of Kolmogorov Complexity

Martin-L¨of (1966) defined the randomreals (elements of 2^ω) as those avoiding certain effective measure zero sets.

(10)

Selective history of Kolmogorov Complexity

Martin-L¨of (1966) defined the randomreals (elements of 2^ω) as those avoiding certain effective measure zero sets.

Levin (1973) and Chaitin (1975) modified Kolmogorov complexity to characterize random sequences. (We will use this modified version.)

(11)

Plain Kolmogorov complexity

Definition

The machine R is calleduniversal if for each machine M, there is a constant eM such that

∀x[CR(x)≤ CM(x) + eM].

(12)

Plain Kolmogorov complexity

Definition

The machine R is calleduniversal if for each machine M, there is a constant eM such that

∀x[CR(x)≤ CM(x) + eM].

Let U : 2^<ω → 2^<ω be a universal machine: Definition (Plain Kolmogorov complexity)

Then the plain Kolmogorov complexity of a string σ with respect to U is

C (σ) := min{|τ | : U(τ ) = σ}

(13)

Martin-L¨of randomness

Idea:^“ Effectively random^” reals (elements of 2^ω) should avoid the

“ effective measure zero^” sets.

(14)

Martin-L¨of randomness

“ effective measure zero^” sets. Definition

A Martin-L¨of testis a uniformly c.e. sequence (Gm)m_∈N of open sets such that∀m ∈ N λGm ≤ 2^−m.

A isML-random if it passes every Martin-L¨of test (Z 6∈^TmGm).

(15)

Martin-L¨of randomness

“ effective measure zero^” sets. Definition

A Martin-L¨of testis a uniformly c.e. sequence (Gm)m_∈N of open sets such that∀m ∈ N λGm ≤ 2^−m.

A isML-random if it passes every Martin-L¨of test (Z 6∈^TmGm).

Fact: Almost all sequences are Martin-L¨of random.

(16)

n-Randomness

There are two ways we could definen-randomness. Definition (I)

Let n > 0. A set Z is calledn-random if Z is ML-random relative to∅ⁿ⁻¹.

(17)

n-Randomness

Definition (II)

A isn-randomif whenever (Gm)m_∈N is a uniform sequence of Σ⁰n

class such that µ(Gm)≤ 2^−m, then A6∈^Ti_∈N^G^m^.

(18)

n-Randomness

Definition (II)

Important observation: a Σ⁰n class is not necessarily open, hence not necessarily a Σ⁰₁[∅ⁿ⁻¹] class.

(19)

n-Randomness

Definition (II)

Important observation: a Σ⁰n class is not necessarily open, hence not necessarily a Σ⁰₁[∅ⁿ⁻¹] class.

However, Kurtz proved that I ⇔ II .

(20)

Weak 2-Randomness

What if we drop the condition that λ(Gm)m_∈N≤ 2^−m ?

(21)

Weak 2-Randomness

What if we drop the condition that λ(Gm)m_∈N≤ 2^−m ? Consider a uniform sequence (Gm)m_∈N of Σ⁰₁ classes such that limiλ(Gm) = 0.

(22)

Weak 2-Randomness

What if we drop the condition that λ(Gm)m_∈N≤ 2^−m ? Consider a uniform sequence (Gm)m_∈N of Σ⁰₁ classes such that limiλ(Gm) = 0. Then^T_mGm is exactly a measure zero Π⁰₂ class.

(23)

Weak 2-Randomness

Definition

A isweak 2-randomif it is in no Π⁰₂ null class.

(24)

Weak 2-Randomness

Definition

A isweak 2-randomif it is in no Π⁰₂ null class. Fact

2-random ⇒ weak 2-random ⇒ 1-random. The reverse implications fail (Kurtz, Kautz).

(25)

Prefix-free (Kolmogorov) complexity

Idea. The^“ information content^” of σ is the length of the shortest description of σ.

(26)

Prefix-free (Kolmogorov) complexity

It is important what kind of descriptions we allow.

(27)

Prefix-free (Kolmogorov) complexity

It is important what kind of descriptions we allow. One approach – due to Levin and Chaitin:

Definition

A⊆ 2^<ω isprefix-free if σ, τ ∈ A implies that σ 6≺ τ (σ is not a proper prefix of τ ).

(28)

Prefix-free (Kolmogorov) complexity

Definition

LetU : 2^<ω→ 2^<ω be universal prefix-free Turing machine .

(29)

Prefix-free (Kolmogorov) complexity

Definition

LetU : 2^<ω→ 2^<ω be universal prefix-free Turing machine . Definition (Prefix-free complexity)

Given a string σ∈ 2^<ω, define the prefix-free Kolmogorov complexity of σ as K (σ) = min{|τ | : U(τ ) = σ}.

(30)

Incompressibility

Prefix-free complexity gives us a nice characterization of 1-randomness.

Theorem (Schnorr)

A is1-randomiff (∀n)K (A ↾ n) ≥ n − O(1).

(31)

Incompressibility

Prefix-free complexity gives us a nice characterization of 1-randomness.

Theorem (Schnorr)

A is1-randomiff (∀n)K (A ↾ n) ≥ n − O(1).

Open Question

Is there an initial segment complexity characterization of weak 2-randomness?

(32)

Counting Theorem

Chaitin showed that the bound given in this theorem is tight, as part of the following result.

Theorem (Counting Theorem)

(1) max{K (σ) : |σ| = n} = n + K (n) ± O(1).

(2) |{σ : |σ| = n ∧ K (σ) ≤ n + K (n) − r }| ≤ 2ⁿ^{−r +O(1)}, where the constant O(1) does not depend on n and r .

(33)

Counting Theorem

Chaitin showed that the bound given in this theorem is tight, as part of the following result.

Theorem (Counting Theorem)

(1) max{K (σ) : |σ| = n} = n + K (n) ± O(1).

(2) |{σ : |σ| = n ∧ K (σ) ≤ n + K (n) − r }| ≤ 2ⁿ^{−r +O(1)}, where the constant O(1) does not depend on n and r .

Note that, For any σ∈ 2^<ω, ^P

σ_∈2^<ω

2^{−K (σ)}≤ ^P

U_{(τ )↓}

2^{−|τ |} ≤ 1 where U is prefix-tree universal Turing machine.

(34)

Some theorems

We proved the following result: Theorem

(∀x)(∃y ) such that K (xy ) > |xy |. Proof.

We use the same technique in the proof of Counting Theorem.

(35)

New theorems

By our theorem,we have following corollary. Corollary

(∃^∞n)K (X ↾ n) > n− O(1) does not imply (∀n)K (X ↾ n) > n − O(1).

(36)

New theorems

Note that, (∀n)K (X ↾ n) > n − O(1) is 1-randomness. But, It is easy to know that 1-randomness imply

(∃^∞n)K (X ↾ n) > n− O(1).

(37)

New theorems

Note that, (∀n)K (X ↾ n) > n − O(1) is 1-randomness. But, It is easy to know that 1-randomness imply

(∃^∞n)K (X ↾ n) > n− O(1).

Question

(∃^∞n)K (X ↾ n) > n− O(1) is an initial segment complexity characterization of KL-randomness?

(38)

Proof sketch of corollary

Proof idea: Construction of X such that:

Step 0: Pick up σ₀ such that: K (σ₀) >|σ0|.

Pick up τ0 such that: K (σ0τ0) <|σ0| + |τ0|.(τ0= (00· · · 0)) Pick up σ₁ such that: K (σ₀τ₀σ₁) >|σ0| + |τ0| + |σ1| − b1

Step n+1: We already construct σ₀, τ₀σ₁,· · · , σⁿ, τn.Let σ^′ = σ₀, τ₀,· · · , σⁿ−1, τn₋₁, σn, and

˜

σ = σ₀, τ₀,· · · , σⁿ−1, τn₋₁, σn, τn such that: K (σ^′) >|σ^′|.

K (˜σ) <|˜σ| − n. Then,

Pick up σn₊₁ such that: K (˜σσn₊₁) >|˜σσn₊₁| by our theorem. Pick up τn₊₁ (τn₊₁= (00· · · 0)) such that:

K (˜σσn+1τn+1) <|˜σσn+1τn+1| − (n + 1). Let X = σ₀, τ₀, σ₁, τ₁,· · · .

(39)

Maximal complexity

Definition (Loveland)

A∈ 2^ω is Kolmogorov randomif

∃^∞n(C (A ↾ n)≥ n − O(1))

This notion was studied earlier in several forms, see Martin-L¨of, Schnorr and Solovay.

(40)

Maximal complexity

Definition (Loveland)

A∈ 2^ω is Kolmogorov randomif

∃^∞n(C (A ↾ n)≥ n − O(1))

This notion was studied earlier in several forms, see Martin-L¨of, Schnorr and Solovay.

Definition (Solovay)

A∈ 2^ω is strongly Chaitin randomif

(∃^∞n)K (A ↾ n)≥ n + K (n) − O(1)

(41)

Relationships between these classes

Theorem (Solovay)

3-random⇒ strongly Chaitin random ⇒ Kolmogorov random.

(42)

Relationships between these classes

Theorem (Solovay)

Theorem (Miller, 2004)

2-random⇒ Kolmogorov random.

(43)

Relationships between these classes

Theorem (Solovay)

Theorem (Nies, Terwijn, stephan, 2005) Kolmogorov random⇒ 2-random.

(44)

Relationships between these classes

Theorem (Solovay)

Theorem (Nies, Terwijn, stephan, 2005) Kolmogorov random⇒ 2-random.

(45)

Notions strongr than ML-randomness

3-random

strongly chaitin random

generalized ML-random

2-random Kolmogorov random

weakly 2-random

ML-random

⇓

⇓ ⇓

m

=⇒

⇐⇒

⇓

=⇒

1-random

⇓

⇐⇒ 6⇑

⇐=

Figure 1.1: Notions strongr than ML-randomness

(46)

New Randomness: X-Randomness

We study randomness notions between Martin-L¨of randomness and 2-randomness.

(47)

New Randomness: X-Randomness

We propose a new definitions of randomness : ML-randomness in any low set. Moreover, Moreover, we will give some truly

fascinating results for our new randomness along this work.

(48)

New Randomness: X-Randomness

fascinating results for our new randomness along this work. Definition

(i) AX-testis a sequence (Gm)m_∈N of open sets, which is uniformly c.e in some low set such that

∀m ∈ N λGm ≤ 2^−m.

(49)

New Randomness: X-Randomness

∀m ∈ N λGm ≤ 2^−m.

(ii) A set Z ⊆ Nfailsthe test if Z ∈^TmGm, otherwise Z passes the test.

(50)

New Randomness: X-Randomness

∀m ∈ N λGm ≤ 2^−m.

(51)

New Randomness: X-Randomness

∀m ∈ N λGm ≤ 2^−m.

(iii) Z isX-randomif Z pass each X-test.

(52)

New Randomness: X-Randomness

By Schnorr’ theorem,there is a characterization of X-randomness via a growth condition on the initial segment complexity. So we can definedX-randomas follows:

(53)

New Randomness: X-Randomness

By Schnorr’ theorem,there is a characterization of X-randomness via a growth condition on the initial segment complexity. So we can definedX-randomas follows:

Definition

A set Z isX-randomif

(∀n)(K^A(Z ↾ n) > n− O(1)) for any set A such that A^′ ≡T φ^′.

(54)

Main theorem

Theorem

The following statements hold:

(i) Every 2-randomness is X-randomness.

(55)

Main theorem

Theorem

(i) Every 2-randomness is X-randomness. (ii) Every X-randomness is ML-randomness.

(56)

Main theorem

Theorem

(i) Every 2-randomness is X-randomness. (ii) Every X-randomness is ML-randomness. (iii) ML-randomness does not imply X-randomness.

(57)

Main theorem

Theorem

(i) Every 2-randomness is X-randomness. (ii) Every X-randomness is ML-randomness. (iii) ML-randomness does not imply X-randomness. (iv) Weak 2-randomness does not imply X-randomness.

(58)

Main theorem

Theorem

(i) Every 2-randomness is X-randomness. (ii) Every X-randomness is ML-randomness. (iii) ML-randomness does not imply X-randomness. (iv) Weak 2-randomness does not imply X-randomness.

(59)

Proof of Main theorem (Sketch)

(i): Every 2-randomness is X-randomness: Suppose X is 2-random, By the definition,

∀n(K^∅(X ↾ n) > n− O(1)). Because, f ≤T ∅^′,

So, K^∅^′(X ↾ n)≤⁺K^f(X ↾ n). Then,∀n(K^f(X ↾ n) > n− O(1)).

(60)

Proof of Main theorem (Sketch)

(ii): Every X-randomness is ML-randomness.: Because, K (X ↾ n)≥⁺K^f(X ↾ n),

So, (∀n)(K^f(X ↾ n) > n− O(1)) ⇒ (∀n)(K (X ↾ n) > n − O(1)).

(61)

Proof of Main theorem (Sketch)

(ii): Every X-randomness is ML-randomness.: Because, K (X ↾ n)≥⁺K^f(X ↾ n),

So, (∀n)(K^f(X ↾ n) > n− O(1)) ⇒ (∀n)(K (X ↾ n) > n − O(1)). (iii): ML-randomness does not imply X-randomness

Fact: ∃ 1-random X such that X^′≡T ∅^′ X is not 1-random in X .

(62)

2-random

X-random weak 2-random Demuth random

1-random

?

? i

ii

iii

iv

(63)

Some theorem

We proof some properties of X-randomness. Proposition

Each low set is not X-random.

(64)

Some theorem

We proof some properties of X-randomness. Proposition

Each low set is not X-random. Proof.

For any set Z , Z is not 1-random in Z . If low set A is X-random, then A is 1-random in A.

(65)

Some theorem

It is not hard to prove the following result. Then we show there is no universal X -test.

Theorem

∀A: low, ∃B: low ,

∃X (X is A-random & X is not B-random).

(66)

Some theorem

Theorem

∃X (X is A-random & X is not B-random). Corollary

There is no universal X -test.

(67)

Some theorem

Theorem

∃X (X is A-random & X is not B-random). Corollary

There is no universal X -test. Proposition

Each X -random set Z satisfies the law of large numbers.

(68)

Questions

Question

X-randomness does not imply 2-randomness ?

(69)

Questions

Question

If this question is true, then X-randomness will lies in between 2-randomness and ML-randomness.

(70)

Questions

Question

If this question is true, then X-randomness will lies in between 2-randomness and ML-randomness.

Also, X-randomness be really different from weak 2-randomness.

(71)

Questions

The following question also be important. Question

Does the Van Lambalgen’theorem hold for X-randomness ?

(72)

Questions

The following question also be important. Question

Does the Van Lambalgen’theorem hold for X-randomness ?

Question

X-random and Demuth random are incomparable ?

(73)

Important work 1999-2005

“ Lowness for the class of random sets^” (1999) by Kucera and Terwijn;

“ R.e. reals and Chaitin Omega numbers^” by Calude, Hertling, Khoussainov, Wang (2001); subsequent paper

“ Randomness and recursive enumerability^” by Kucera and Slaman (2001);

“ Trivial reals^” by Downey, Hirschfeldt, Nies, Stephan (2003).

“ Lowness properties and randomness^” by Nies (published 2005).

(74)

Lowness properties and Randomness

In this section, We study three lowness properties that will later turn out to be equivalent: low for ML-randomness, low for K , and a base for ML-randomness.

(75)

Lowness properties and Randomness

Further, we will introduce the K-trivial sets which are far from random.

(76)

Lowness properties and Randomness

Then, we will use this properties to show that weak 2-randomness does not imply X randomness.

(77)

Lowness properties and Randomness

Then, we will use this properties to show that weak 2-randomness does not imply X randomness.

ALowness properties of a real A says that, in some sense, A how computational power when used as an oracle.

(78)

Recall: K (x) = length of a shortest prefix free description of string x.

A set is K-trivial via a constant b if

∀nK (A ↾ n) ≤ K (n) + b. Let K denote that class of K-trivial sets. (Chaitin, 1975).

A islow for ML-randomnessif each ML-random set is already ML-random relative to A (Zambella, 1990).

We will see that these two concepts are equivalent.

(79)

More concepts

Further lowness properties have introduced:

Base for ML-randomness (Kuˇcera, APAL 1993). Low for K (Muchnik jr., in a Moscow seminar, 1999). Low for K ⇒ Low for MLK-randomness ⇒ Base for ML-randomness.

(80)

Base for ML-randomness

LetMLRdenote the class of Martin-L¨of-random sets. We will call such a set A abase for ML-randomness:

A≤T Z for someZ ∈ MLR^A . They were studied by Kuˇcera (1993).

A is low for ML-randomness then A is base for ML-randomness.

For, there is a ML-random Z such that A≤T Z . Then Z is ML-random relative to A.

(81)

Two theorem

(1) Each base for ML-randomness is low for K .(Hirschfeldt, Nies,Stephan, 2007).

(2) Each K -trivial set is low for K . (Nies,Hirschfeldt, 2005). We have already seen the easy implications:

Low for K ⇒ Low for MLK-randomness ⇒ Base for ML-randomness.

Low for K ⇒ K-trivial.

Then, by Theorem (1), all three classes are the same. by Theorem (2), all four classes are the same.

(82)

Low for K easy

K-trivial

easy Low for ML easy

Base for ML

Harder

Very hard

(83)

Proof Sketch

In proving part (iv) of main theorem, we will use the following theorems:

Theorem (Downey, Nies, Weber, and Yu, (2008)) Low(W2Rand, MLRand) = Low(MLRand).

In other words, if each weakly 2 random is Martin-L¨of random relative to A, then A is in fact low for Martin-L¨of randomness.

(84)

Proof Sketch

In proving part (iv) of main theorem, we will use the following theorems:

Theorem (Downey, Nies, Weber, and Yu, (2008)) Low(W2Rand, MLRand) = Low(MLRand).

In other words, if each weakly 2 random is Martin-L¨of random relative to A, then A is in fact low for Martin-L¨of randomness.

Theorem (Nies,2005)

Each K-trivial set A is superlow.

Theorem (Bickford/Mills and Mohrherr (1986))

(85)

Proof (iv) of Main theorem

Putting above facts together,we get following fact.

(86)

Proof (iv) of Main theorem

Putting above facts together,we get following fact. Fact

If each weakly 2 random is ML-random relative to A, then A is superlow.

(87)

Proof (iv) of Main theorem

Putting above facts together,we get following fact. Fact

If each weakly 2 random is ML-random relative to A, then A is superlow.

Proof of Weak 2-randomness does not imply X-randomness: Assume that∀X (X is weak 2-random ⇒ X is X-random). Pick up A be low but not superlow.

Then, by our assumption:

Any weak 2-random X is 1-random in A. By above fact, A should be superlow. This contradiction.

(88)

Thank you very much!