Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

A generalization of Levin/Schnorr’s theorem.

Keita Yokoyama.
Japan Advanced Institute of Science and Technology

May 14, 2013, University of Tokyo

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

1 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Outline1

Introduction
Randomness
Complexity
Correspondence

2

Generalizations of randomness/complexity
Generalized randomness
Generalized complexity

3

A generalization of Levin/Schnorr’s theorem
Generalized correspondence
Characterizing basic properties

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

2 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Outline1Introduction
Randomness
Complexity
Correspondence

2

Generalizations of randomness/complexity
Generalized randomness
Generalized complexity

3

A generalization of Levin/Schnorr’s theorem
Generalized correspondence
Characterizing basic properties

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

3 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Maritin-Löf randomness
Measure theoretic approach for randomness:
Let µ be a fair-coin measure on 2ω .
For given A ⊆ 2<ω , [A ] := {X ∈ 2ω | ∃σ ∈ A σ ⊆ X }.
A sequence {An ⊆ 2<ω }n∈ω is (uniformly) c.e. if{(σ, n) | σ ∈ An } is c.e.

Definition
A c.e. sequence {An }n∈ω is said to be a Martin-Löf test (ML-test) ifµ([An ]) ≤ 2−n .
!
A real X is said to be a Maritin-Löf random if X ! n [An ] for any
ML-test {An }n∈ω .

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

4 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Partial randomness
We can generalize the previous notion of randomness:
instead of using measure, we use “weight functions”.
Let h : 2<ω → ω be a computable function.
For A ⊆ 2<ω , definedwth (A ) ="2−h (σ) .

σ∈AA set P ⊆ 2<ω is said to be prefix-free if∀σ, τ ∈ P (σ ⊆ τ ⇔ σ = τ).
For A ⊆ 2<ω , define

pwth (A ) = sup{dwth (P ) | P is a prefix-free subset of A }.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

5 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Partial randomness

Definition
A c.e. sequence {An }n∈ω is said to be an h -test if dwth (An ) ≤ 2−n .
!
A real X is said to be an h -random if X ! n [An ] for any h -test{An }n∈ω .
.
Definition
A c.e. sequence {An }n∈ω is said to be a strong-h -test ifpwth (An ) ≤ 2−n .
!
A real X is said to be a strong-h -random if X ! n [An ] for. any
strong-h -test {An }n∈ω .

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

6 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Prefix-free complexity
A Turing machine (partial computable function)
M : ⊆2<ω → 2<ω is said to be prefix-free if dom(M ) isprefix-free.
A prefix-free Turing machine U is said to be universal if for any
prefix-free Turing machine M , there exists τ ∈ 2<ω such that
M (σ) = U (τ$ σ).
There exists a universal prefix-free Turing machine.
Definition (prefix-free complexity)
The prefix-free complexity KP : 2<ω → ω is define as follows:

KP(σ) := min{|τ| | U (τ) = σ},where U is a prefix-free universal Turing machine.
Note that this is well-defined up to constant.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

7 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Prefix-free complexity
Using a complexity function, we can say that a real X iscomplex/random if it is not compressible:Definition
A real X ∈ 2ω is said to be weakly Chaitin random or KP-complex ifthere exists c ∈ ω such that for any n ∈ ω,KP(X ! n) ≥ n − c .
Similarly, if h : 2<ω → ω be a computable function, then X ∈ 2ω issaid to be KP-h-complex if there exists c ∈ ω such that for anyn ∈ ω,KP(X ! n) ≥ h (X ! n) − c .
Keita Yokoyama.

A generalization of Levin/Schnorr’s theorem

8 / 32Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Characterization by the Kraft inequality
KP can be characterized as a minimal (abstract) complexity which
satisfies the following Kraft inequality.
Proposition (the Kraft ienequality)"2−KP(σ) < 1.

σ∈2<ωA function K : 2<ω → ω ∪ {∞} is said to be an abstract
complexity if K is right c.e., or equivalently, there exists a c.e.
set A ⊆ 2<ω × ω such that K (σ) = min{n | (σ, n) ∈ A }. .

.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

9 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Characterization by the Kraft inequality
Theorem (the Kraft/Chaitin theorem)

For any abstract complexity K such that"
2−K (σ) < 1,σ∈2<ω

there exists c ∈ ω such that for any σ ∈ 2<ω ,K (σ) ≥ KP(σ) − c .

.
This theorem means that KP is minimal up to constant in all
abstract complexities which satisfy the Kraft inequality.
In fact, several complexity functions can be defined in this way.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

10 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Several other complexities
Definition (Uspensky/Shen)
The a priori complexity KA is defined as a minimal complexity
which satisfies the following:#for any prefix-free P ⊆ 2<ω , σ∈P 2−K (σ) < 1.
The simple complexity KS is defined as a minimal complexity
which satisfies the following:{σ ∈ 2<ω | K (σ) < n}# < 2n .
The decision complexity KD is defined as a minimal
complexity which satisfies the following:
for any prefix-free P ⊆ 2<ω , {σ ∈ P | K (σ) < n}# < 2n .
.
We can also define KA-h-complex, KS-h-complex andKD-h-complex similarly to KP-h -complex.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

11 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Levin/Schnorr’s theorem
The previous two definitions of randomness have a nicecorrespondence.
Theorem (Levin/Schnorr’s theorem)A real X ∈ 2ω is ML-random if and only if it is KP-complex.
More generally, the following holds.
Theorem (Tadaki/Calude/Staiger/Terwijn).

Let h : 2<ω → ω be a computable function.

.
A real X ∈ 2ω is h-random if and only if it is KP-h-complex.
A real X ∈ 2ω is strongly-h-random if and only if it isKA-h-complex.

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

12 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Levin/Schnorr’s theorem
For KS and KD, we need new weight functions.
Let h : 2<ω → ω be a computable function.
For A ⊆ 2<ω , define

dcth (A ) = sup{σ ∈ A | h (σ) < n}# /2n .
n∈ω

For A ⊆ 2<ω , define

pcth (A ) = sup{dcth (P ) | P is a prefix-free subset of A }.
We can define dcth -randomness or pcth -randomness similar toh -randomness or strong-h -randomness.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

13 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Randomness
Complexity
Correspondence

Levin/Schnorr’s theorem

Then, we have the following.
Theorem (Some more variations)

Let h : 2<ω → ω be a computable function.

A real X ∈ 2ω is h-random if and only if it is KP-h-complex.
A real X ∈ 2ω is strongly-h-random if and only if it isKA-h-complex.

A real X ∈ 2ω is dcth -random if and only if it is KS-h-complex.

A real X ∈ 2ω is pcth -random if and only if it is KD-h-complex.
.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

14 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

We have seen that there are several versions ofrandomness/complexity defined by a “measure-like”
function/complexity function.
Questions.
Is there a generalization of all of these randomness orcomplexity notions?
Can we generalize the correspondence of randomness andcomplexity?

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

15 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Outline1

Introduction
Randomness
ComplexityCorrespondence

2

Generalizations of randomness/complexity
Generalized randomness
Generalized complexity

3

A generalization of Levin/Schnorr’s theorem
Generalized correspondence
Characterizing basic properties

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

16 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Weight function
We first generalize a notion of randomness defined by a wightfunction.
Definition
A weight function is a computable function m : [2<ω ]<ω → [0, ∞)which satisfies the following:1m(∅) = 0,2if F1 ⊆ F2 , then m(F1 ) ≤ m(F2 ),3m(F1 ∪ F2 ) ≤ m(F1 ) + m(F2 ).

For arbitrary A ⊆ 2<ω , we expand m : [2<ω ]≤ω → [0, ∞) as follows:.
.

m(A ) = sup{m(F ) | F ⊆fin A }.
Note that m(A ) = inf{#i ∈ω m (Fi ) |Keita Yokoyama$i ∈ω Fi ⊇ A } if m is bounded.

.

A generalization of Levin/Schnorr’s theorem

17 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Randomness defined by a weight function
All of the following are weight functions:dwth (F ) :="2−h (σ) ,σ∈Fpwth (F ) := sup{dwth (P ) | P ⊆ F is prefix free},{σ ∈ F | h (σ) < n}#,2nn∈ωpcth (F ) := sup{dcth (P ) | P ⊆ F is prefix free}.
dcth (F ) := supDefinition
An m-test is a c.e. sequence {Ai }i ∈ω such that m(Ai ) ≤ 2−i .
!
A real X ∈ ω is said to be m-random if X ! i [Ai ] for any m-test{Ai }i ∈ω .
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

18 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Universal test

Proposition

For any weight function m, a universal m-test exists,i.e., there exists an m-test {Ai }i ∈ω such that X ∈ 2ω is m-random if!
and only if X ! i [Ai ].
Corollary.

The class of all m-random reals is Σ02 .
.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

19 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

In fact, any Σ02 -subclass of Cantor space can be considered as aset of m-random reals as follows:
Let P ⊆ 2ω be a Σ02 -class. Take a computable sequence of trees{Ti | i ∈ ω} such that X ∈ P if and only if X is a path of Ti for somei ∈ ω. Define weight functions mi and m as follows:1 if F ∩ Ti " ∅,mi (F ) = 
0 otherwise,"m(F ) =2−i mi (F ).
i ∈ωThen, we can easily check that X is m-random if and only if X ∈ P .

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

20 / 32Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Rule for a complexity
Next, we generalize complexity functions.
For this, we consider a generalization of the Kraft/Chaitin theorem.
A finite complexity function is a finite set r ⊆ 2<ω × Z,
we identify r as a function K r (σ) = min{d | (σ, d ) ∈ r } ∪ {∞}.
Given a finite complexity r ⊆ 2<ω × Z,r̊ := {σ ∈ 2<ω | ∃d ∈ ω (σ, d ) ∈ r },r +i := {(σ, d + i ) | (σ, d ) ∈ r },given a computable function h : 2<ω → ω,r +h := {(σ, d + h (σ)) | (σ, d ) ∈ r }.
Let r , s ⊆ 2<ω × ω be finite complexity functions.
We say that r is stronger than s (s ≺ r ) if K s (σ) ≤ K r (σ) for
any σ ∈ 2<ω .
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

21 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Rule for a complexity
Now, we construct a complexity function from finite complexity
functions.
Definition
A rule (for a complexity function) is a computable set
R ⊂ [2<ω × Z]<ω which satisfies the following:123.

∅ ∈ R.

If r ∈ R and s ≺ r , then s ∈ R .

If r , s ∈ R , then (r ∪ s )+1 ∈ R .

Condition 3 means that any two finite complexity functions can be
combined into one function with an additional step.
.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

22 / 32Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Optimal complexity function
Definition (Complexity as a minimal function)
A complexity function is a right c.e. function K : 2<ω → Z.

Given a rule R , a complexity function K = KR is said to be
R-optimal if
12R -function: for any finite F ⊆ 2<ω , {(σ, K (σ)) | σ ∈ F } ∈ R .

R -minimal: if K 2 is also an R -function, then there exists c ∈ ωsuch that for any σ ∈ 2<ω ,K 2 (σ) ≥ K (σ) − c .

.
.

.

Note that KR is defined uniquely up to constant.
Proposition

For any rule R, R-optimal complexity function KR exists.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

23 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized randomness
Generalized complexity

Complex defined by a complexity function
Definition
X ∈ 2ω is said to be R -complex if there exists c ∈ ω such thatKR (X ! n) ≥ n − c for any n ∈ ω.
.

Examples.

#Let RKP := {r ∈ [2<ω × Z]<ω | σ∈2<ω 2−Kr (σ) < 1}, then,
KP is an RKP -optimal complexity.
.
+|·|−hLet RKPh := RKP= {r +|·|−h | r ∈ RKP }, then,KRKPh (σ) = KP(σ) + |σ| − h (σ),
i.e., X is RKPh -complex iff it is KP-h -complex.

We can define RKAh , RKSh , and RKDh similarly.

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

24 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized correspondence
Characterizing basic properties

Outline1

Introduction
RandomnessComplexity
Correspondence

2

Generalizations of randomness/complexity
Generalized randomness
Generalized complexity

3

A generalization of Levin/Schnorr’s theorem
Generalized correspondence
Characterizing basic properties

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

25 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized correspondence
Characterizing basic properties

Generalized correspondence
Now, we construct a concrete correspondence of randomness andcomplexity.
For r ∈ [2<ω × Z]<ω ,3r 3 := min{|σ| − d | (σ, d ) ∈ r } ∈ Z ∪ {∞} (3∅3 = ∞).
We can easily check that s ≺ r if s̊ ⊆ r̊ and 3s 3 ≤ 3r 3.

Definition
Letm be a weight function,and let R be a rule. Then, we define√√<ω<ωm ⊆ [2 × Z] and R : [2<ω ]<ω → [0, ∞) as follows:√√

m := {r ∈ [2<ω × Z]<ω | ∀s ⊆ r m(s̊ ) ≤ 2−3s 3 },R (F ) := inf{2−3r1 3 + · · · + 2−3rl 3 | r1 , . . . , rl ∈ R , F ⊆ r˚1 ∪ · · · ∪ ˚rl }.
√√We can check that m is a rule and R is a weight function.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

26 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized correspondence
Characterizing basic properties

Generalized correspondence
Proposition

Let m be a weight function, and let R be a rule. Then,
12.
.

m≤m

√√

√√

≤ 2m,

R ⊆ R ⊆ R −2 = {s | ∃r ∈ R s ≺ r −2 },thus, KR − c ≤ KR √√ ≤ KR + c for some c ∈ ω.

.

Definition
Let m be a weight function, and let R be a rule.
Then, R is said to be a dual rule of m, or m is said to be a dual
weight function of R ,.
if there exists c ∈ ω such that KR − c ≤ Km√ ≤ KR + c , √or equivalently, there exists c > 0 such that 1/c · m ≤ R ≤ cm.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

27 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized correspondence
Characterizing basic properties

Generalized correspondence
Now, we have the following.
Theorem (Generalized Levin/Schnorr’s theorem)

Let m be a weight function, and let R be its dual rule. Then, X ∈ 2ωis m-random if and only if it is R-complex.
We can easily check the following:.

RKPh is a dual of dwth ,RKAh is a dual of pwth ,RKSh is a dual of dcth ,RKDh is a dual of pcth .

Keita Yokoyama.

A generalization of Levin/Schnorr’s theorem

28 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Generalized correspondence
Characterizing basic properties

Characterizing basic properties
We can characterize some basic properties of randomness:
Non-triviality:
X is not m-random relative to X

⇔limn→∞ sup{m({σ}) | n < |σ|} = 0.

Tail invariance:
X is m-random iff its tail is m-random⇔√√∀τ ∈ 2<ω ∃c ∈ ω r ∈ m → {(τ$ σ, d + c ) | (σ, d ) ∈ r } ∈ m .

Next, we focus on the property of relativization to a complete
Π01 -class.
This is related to behaviors of randomness in arithmetic.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

29 / 32

Introduction
Generalizations of randomness/complexityA generalization of Levin/Schnorr’s theorem

Generalized correspondence
Characterizing basic properties

Monotonicity and propagation to CPA
For A , B ⊆ 2<ω , we write A ≺ B if for any σ ∈ A there existsτ ∈ B such that τ ⊆ σ.
A weight function m is said to be monotonic if for any
A , B ⊆ 2<ω , m(A ) ≤ m(B ) if A ≺ B .

For a given weight function m, define a monotonic closure m∗of m asm∗ (F ) := inf{m(C ) | C ⊆ 2<ω , F ≺ C }.
Theorem
Let m be a weight function. Then, the following are equivalent.
1

X is m∗ -random.

2

X is m∗ -random relative to CPA.

3

X is m-random relative to CPA.
Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

30 / 32

Introduction
Generalizations of randomness/complexity
A generalization of Levin/Schnorr’s theorem

Questions

Can we characterize specific properties of randomness?
What is needed for the van Lambalgen theorem?
What is needed for the ample excess lemma?
...
Question
Which condition is needed to define “randomness”?

Keita Yokoyama

A generalization of Levin/Schnorr’s theorem

31 / 32