ファイル置き場 Sendai Logic Homepage speaker12

The inner structures of Turing upward closures

Takayuki Kihara

Mathematical Institute, Tohoku University

February 22, 2012

Joint work with Kojiro Higuchi

Nonuniform Computability

Every computable function is continuous!

Takayuki Kihara The inner structures of Turing upward closures

Every computable function is continuous!

Is there a way to handle discontinuous functions in

Computability Theory?

Nonuniform Computability

Every computable function is continuous!

Is there a way to handle discontinuous functions in

Computability Theory?

Nonuniformly computable functions are, in general,

discontinuous!

A function f is nonuniformly computable

if f(x) ≤

x for any x ∈ dom(f).

Takayuki Kihara The inner structures of Turing upward closures

Every computable function is continuous!

Is there a way to handle discontinuous functions in

Computability Theory?

Nonuniformly computable functions are, in general,

discontinuous!

A function f is nonuniformly computable

if f(x) ≤

x for any x ∈ dom(f).

There is a huge gap between

“computability” and “nonuniform computability”.

Nonuniform Computability

Every computable function is continuous!

Is there a way to handle discontinuous functions in

Computability Theory?

Nonuniformly computable functions are, in general,

discontinuous!

A function f is nonuniformly computable

if f(x) ≤

x for any x ∈ dom(f).

There is a huge gap between

“computability” and “nonuniform computability”.

To fill the gap, we introduce notions between them,

(α, β, γ) -computability for each α, β, γ ≤ ω .

(1, 1, 1)-computable = computable,

(ω, ω, ω)-computable = nonuniformly computable.

Takayuki Kihara The inner structures of Turing upward closures

Learnability

( 1 , 1 ) (uniformly) computable

( 1 , n ) learnable with mind-changes < n

( 1 , ω, n ) learnable with error < n

( 1 , ω) learnable

( n , 1 ) n-wise computable

( n , ω) team-learnable via n-learners

(ω, 1 ) nonuniformly computable

Remark

The notion of learnability is introduced by Gold (1965).

The notions of learnability and n-wise computability on topological

spaces naturally arises in many area of mathematics such as Linear

Algebra and Functional Analysis (Brattka, Ziegler et al. 2000’s)

Nonuniform Computability

Constructive Principle

( 1 , 1 ) constructive

( 1 , 2 ) Σ ⁰

1 ^-LEM

( 1 , ω, 2 ) Unique Σ ⁰

2 ^-LLPO

( 1 , ω) Σ ⁰

2 ^-DNE

( 2 , 1 ) Σ ⁰

2 ^-LLPO

( 2 , ω) (Σ ⁰

2 ^{∧ Π}

0

2 ^{) -LLPO}

(ω, 1 ) Σ ⁰

3 ^-DNE

Remark

An arithmetical hierarchy for LEM/LLPO/DNE are introduced by Akama,

Kohlenbach et al (2004). Here,

LEM: φ ∨ ¬φ (law of excluded middle).

LLPO: [¬(φ ∧ ψ)] → [¬φ ∨ ¬ψ] (lessor limited principle of omniscience).

DNE: ¬¬φ → φ (double negation elimination).

Takayuki Kihara The inner structures of Turing upward closures

Topological Games

( 1 , 1 ) Wadge games

( 1 , n ) Backtrack games (with n-backtracks)

( 1 , ω, n ) Multitape games (with n-tapes and finite moves)

( 1 , ω) Backtrack games

( n , 1 ) Multitape games (with n-tapes)

( n , ω) Backtrack multitape games (with n-tapes)

(ω, 1 ) Multitape games

Remark

Wadge game is introduced by Wadge (1983).

Backtrack/Multitape/Eraser Wadge games are used to characterize a

hierarchy of Borel measurable functions (Andretta 2006/Semmes

2007,2009/Motto Ros 2011).

Backtrack Tarski games capture the positive arithmetical fragment of

Limit Computable Mathematics (Berardi/Coquand/Hayashi 2010).

Nonuniform Computability

Piecewise Computability

( 1 , 1 ) —

( 1 , < ω) finite Π ⁰

1 ^d-layer

( 1 , ω, < ω) finite ∆ ⁰

2 ^{/ Σ}

0

2 partition/layer/cover

( 1 , ω) uniform Π ⁰

1 ^{/ Σ}

0

2 partition/layer/cover

(< ω, 1 ) finite partition

(< ω, 1 ) -tt finite Π ⁰

1 ^cover

(< ω, ω) finite partition + Π ⁰

1 ^{/ Σ}

0

2 partition/layer/cover

(ω, 1 ) infinite partition

(ω, 1 ) -tt Π ⁰

1 ^cover

Remark

Many results are known on the relationship between piecewise continuity

and Borel measurability (Jayne-Rogers 1982/Motto Ros 2010).

Layerwise computability is also used to characterize L

-computability

(Hoyrup-Rojas 2009/ and the next talk...)

Takayuki Kihara The inner structures of Turing upward closures

Definition

Let X , Y be topological T ₀ spaces with countable bases.

A computable sequence ( f _i , r _i ) _i∈ω is good if

f _i : X → Y and r _i : X → ω are partial computable.

For any ξ ∈ X , if r _i (ξ) = r _j (ξ) then f _i (ξ) = f _j (ξ) .

Definition

α, β, γ ≤ ω . A function f : X → Y is (α, β, γ) -computable if

(∃{( f ^e

i ^{, r}

e

i ^{) i∈ω } e<α with good ( f}

e

i ^{, r}

e

i ^{) i∈ω} )(∀ξ ∈ dom( f ))(∃ e < α)

f (ξ) is the limit of { f ^e

i ^{(ξ)} i∈ω ,}

#{ n ∈ ω : r _n ^e (ξ) , r ^e

n+1 (ξ)} < β ,

#{ r _n ^e (ξ) : n ∈ ω} < γ .

If β = γ , then it is called (α, β) -computable.

Nonuniform Computability

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

ξ Y

f (ξ) ?

f (ξ) ?

f

f (ξ) ?

f (ξ) ?

What is the value of f (ξ) ?

Takayuki Kihara The inner structures of Turing upward closures

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

0 ^(ξ)

f ¹

0 ^(ξ)

Guessing the value of f (ξ) : Step 0

Nonuniform Computability

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

1 ^(ξ)

f ¹

1 ^(ξ)

Guessing the value of f (ξ) : Step 1

Takayuki Kihara The inner structures of Turing upward closures

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

2 ^(ξ)

f ¹

2 ^(ξ)

Guessing the value of f (ξ) : Step 2

Nonuniform Computability

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

3 ^(ξ)

f ¹

3 ^(ξ)

Guessing the value of f (ξ) : Step 3

Takayuki Kihara The inner structures of Turing upward closures

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

4 ^(ξ)

f ¹

4 ^(ξ)

Guessing the value of f (ξ) : Step 4

Nonuniform Computability

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

5 ^(ξ)

f ¹

5 ^(ξ)

Guessing the value of f (ξ) : Step 5

Takayuki Kihara The inner structures of Turing upward closures

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

6 ^(ξ)

f ¹

6 ^(ξ)

Guessing the value of f (ξ) : Step 6

Nonuniform Computability

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

f ⁰

7 ^(ξ)

f ¹

7 ^(ξ)

Guessing the value of f (ξ) : Step 7

Takayuki Kihara The inner structures of Turing upward closures

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

lim _n f _n ⁰ (ξ)

lim _n f _n ¹ (ξ)

End of Guessing Procedure

Nonuniform Computability

f : X → Y is ( 2 , 5 , 3 ) -computable via { f ⁰

i ^{, r}

0

i ^{; f}

1

i ^{, r}

1

i ^{} i∈ω}

X

Y

ω

ω

ξ

r ¹

r ⁰ _f ⁰

f ¹

lim _n f _n ⁰ (ξ)

lim _n f _n ¹ (ξ)

f (ξ) = lim _n f _n ⁰ (ξ) or f (ξ) = lim _n f _n ¹ (ξ)

Takayuki Kihara The inner structures of Turing upward closures

Definition (Restated)

Let X , Y be topological T ₀ spaces with countable bases.

A computable sequence ( f _i , r _i ) _i∈ω is good if

f _i : X → Y and r _i : X → ω are partial computable.

For any ξ ∈ X , if r _i (ξ) = r _j (ξ) then f _i (ξ) = f _j (ξ) .

Definition (Restated)

α, β, γ ≤ ω . A function f : X → Y is (α, β, γ) -computable if

(∃{( f ^e

i ^{, r}

e

i ^{) i∈ω } e<α with good ( f}

e

i ^{, r}

e

i ^{) i∈ω} )(∀ξ ∈ dom( f ))(∃ e < α)

f (ξ) is the limit of { f ^e

i ^{(ξ)} i∈ω ,}

#{ n ∈ ω : r ^e

n ^{(ξ) , r}

e

n+1 (ξ)} < β ,

#{ r _n ^e (ξ) : n ∈ ω} < γ .

If β = γ , then it is called (α, β) -computable.

Nonuniform Computability

Proposition

α, β, γ ≤ ω . Every (α, β, γ) -computable function f is

nonuniformly computable, i.e., f (ξ) ≤ _T ξ for any ξ ∈ dom( f ) .

Uniformly computable

⇐⇒ ( 1 , 1 ) -computable

=⇒ (α, β, γ) -computable

=⇒ nonuniformly computable.

Takayuki Kihara The inner structures of Turing upward closures

Definition

Let C ^α

β|γ be the least monoid (under composition) containing all

(α, β, γ) -computable functions.

Theorem

#{C ^α

β|γ : α, β, γ ≤ ω} = 7.

⊆ ^{C <ω} ₁ ^⊆

C ¹

1 ^{⊆ C}

1

<ω ^{⊆ C}

1

ω|<ω ^C

<ω

ω ^{⊆ C}

ω

⊆ _C 1 1

ω ^⊆

Nonuniform Computability

Learnability

( 1 , 1 ) (uniformly) computable

( 1 , n ) learnable with mind-changes < n

( 1 , ω, n ) learnable with error < n

( 1 , ω) learnable

( n , 1 ) n-wise computable

( n , ω) team-learnable via n-learners

(ω, 1 ) nonuniformly computable

Remark

A function f is learnable (or identifiable) if, via an algorithm, from

ξ ∈ dom(f), we can eventually learn a law characterizing f (ξ).

Takayuki Kihara The inner structures of Turing upward closures

Definition ( F : monoid.)

X ≤ _F Y if there is a function f ∈ F with f : Y → X .

Intuition of ≤ _F

Let us think of X and Y as solution sets of some mathematical

problems. X ≤ _F Y means that:

by using some method in F , if we know a solution to Y , then we

can also find a solution to X .

C ¹

1 induces the Medvedev reducibility,

C ^ω

1 induces the Muchnik reducibility.

Nonuniform Computability

Let F and G be some subclasses of nonuniformly computable

functions. How does F differ from G ?

Separating F and G

(LEVEL 1) As functions:

F \ G , ∅ .

(LEVEL 2) As problem-solving methods:

≤ _F \ ≤ _G , ∅ , i.e., (∃ X , Y ⊆ N ^N ) Y ≤ _F X  G Y .

(LEVEL 3) As solving methods for Π ⁰

1 mass problems:

(∃Π ⁰

1 ^{X , Y ⊆ N}

N _{) Y ≤}

F ^{X } G ^{Y .}

(LEVEL 4) Strongest possible separation:

(∀Π ⁰

1 ^{Y ⊆ N}

N _)(∃Π 0

1 ^{X ⊆ N}

N _{) Y ≤}

F X  G Y .

Takayuki Kihara The inner structures of Turing upward closures

Theorem

1

(Ziegler 2009) LEVEL1 separations succeed among these

notions of nonuniform computability.

2

(Higuchi/K. CiE2009 talk) LEVEL3 separations succeed

among these notions of nonuniform computability.

Theorem (Higuchi/K.; This workshop 2011 talk)

(1;1) (1;<!) (1;!;<!)

(<!;1) (1;!)

(<!;!) (!;1)

LEVEL4 separations succeed for red lines.

LEVEL3 separations succeed but LEVEL4 separations does

not succeed for blue lines.

Nonuniform Computability

Remark

“The strongest possible separation theorem” is proved via

Medvedev/Muchnik-style mass-problem-interpretation of Limit

Computable Mathematics (LCM).

LCM = Mathematics based on Learning Theory (Hayashi 2002?)

LCM ≈ Peano arithmetic + ω-rule ⁻ exchange rules

(Berardi/Yamagata 2008)

LCM ≈ Heyting arithmetic + ω-rule + Σ

law of excluded middle

(Tatsuta/Berardi 2011)

Keywords

Learning Theory

Constructive Mathematics

Takayuki Kihara The inner structures of Turing upward closures

Constructive Principle

( 1 , 1 ) constructive

( 1 , 2 ) Σ ⁰

1 ^-LEM

( 1 , ω, 2 ) Unique Σ ⁰

2 ^-LLPO

( 1 , ω) Σ ⁰

2 ^-DNE

( 2 , 1 ) Σ ⁰

2 ^-LLPO

( 2 , ω) (Σ ⁰

2 ^{∧ Π}

0

2 ^{) -LLPO}

(ω, 1 ) Σ ⁰

3 ^-DNE

Nonuniform Computability

Akama/Berardi/Hayashi/Kohlenbach Hierarchy (2004)

Σ

-LEM

Σ

-DNE Σ

-LLPO

∆

2

^-LEM

Σ

-LEM

Remark

LEM: φ ∨ ¬φ (law of excluded middle).

LLPO: [¬(φ ∧ ψ)] → [¬φ ∨ ¬ψ] (lessor limited principle of omniscience).

DNE: ¬¬φ → φ (double negation elimination).

Takayuki Kihara The inner structures of Turing upward closures

Definition (Weihrauch 1992)

F , G: partial multi-valued functions ⊆ X ⇒ Y .

F is Weihrauch reducible to G (written as F ≤ _W G) if there are

computable functions h , k s.t.

(∀ x ∈ dom( F ))(∀ y ∈ G ( h ( x ))) k ( x , y ) ∈ F ( x ) .

x

h

Problem G ( h ( x ))

y

k

Problem F ( x )

k ( x , y )

Nonuniform Computability

Theorem

1

_{f is ( 1 , 2 )} -computable iff f ≤ _W Σ ⁰

1 ^-LEM.

2

_{f is ( 1 , ω, 2 )} -computable iff f ≤ _W Unique Σ ⁰

2 ^-LLPO.

3

_{f is ( 1 , ω)} -computable iff f ≤ _W Σ ⁰

2 ^-DNE.

Theorem (P: any Π ⁰

2 set, Q: any set.)

1

The following are equivalent:

f : Q → P via a (2, 1)-computable f .

f : Q → P via f ≤

Σ

-LLPO.

2

The following are equivalent:

f : Q → P via a (2, ω)-computable f .

f : Q → P via f ≤

_(Σ

2

^{∧ Π}

2

^)-LLPO.

The following are equivalent:

f : Q → P via a (ω, 1)-computable f .

f : Q → P via f ≤

Σ

-DNE.

Takayuki Kihara The inner structures of Turing upward closures

Σ

-DNE

(Σ

)

-LLPO

Σ

-LEM

Σ

2

^{-LLPO Σ}

0 2

^-DNE

UniqueΣ

2

^-LLPO

Σ

-LEM

[C

]

1

[C

]

(team learnable)

[C

]

1

^[C

^]

1

ω

^(learnab

[C

]

ω|2

[C

]

(nonuniformly computable)

H

(non-Lipschitz

hyperconcatenation)

LEM: φ ∨ ¬φ (law of excluded middle).

LLPO: [¬(φ ∧ ψ)] → [¬φ ∨ ¬ψ] (lessor limited principle of omniscience).

DNE: ¬¬φ → φ (double negation elimination).

Nonuniform Computability

DNR _k = { f ∈ k ^N : f ( e ) , Φ e ( e )} .

Theorem (Jockusch 1987)

1

_{There is no} uniformly computable f : DNR ₃ → DNR ₂ .

2

_{There is a} nonuniformly computable f : DNR ₃ → DNR ₂ .

Theorem

1

_{There is no} learnable f : DNR ₃ → DNR ₂ .

2

_{There is no} n-wise computable f : DNR ₃ → DNR ₂ .

3

_{There is a} team-learnable f : DNR ₃ → DNR ₂ .

DNR

can be think of as the parallelization of Σ

-LLPO

:

[¬(φ

∧ φ

) ∧ ¬(φ

∧ φ

) ∧ ¬(φ

∧ φ

)] → ¬φ

∨ ¬φ

∨ ¬φ

.

Takayuki Kihara The inner structures of Turing upward closures

Proof (Sketch)

1

_{There is no} learnable f : DNR ₃ → DNR ₂ :

(Blum-Blum 1975) every learnable f has a Blum-Blum locking

clopen set C, i.e., f |

is computable.

DNR

∩ C is computably homeomorphic to DNR

.

2

_{There is no} n-wise computable f : DNR ₃ → DNR ₂ :

By LEVEL4 non-separation result between C

and C

1

^.

_{There is a} team-learnable f : DNR ₃ → DNR ₂ :

Jockusch’s theorem can be formalized in Σ

-LEM.

Nonuniform Computability

Theorem (Brattka-Pauly-le Roux 201X)

F ⋆ G = max _≤

{ F ^∗ ◦ G ^∗ : F ^∗ ≤ _W F & G ^∗ ≤ _W G } always exists.

Theorem

1

_{DNR 2  W Σ} ⁰

2 ^{-DNE ⋆ DNR 3 .}

2

_DNR

2 ^ W ^{Σ 0} ₂ ^{-LLPO ⋆ DNR} 3 ^.

3

_{DNR 2 ≤ W Σ} ⁰

2 ^{-LEM ⋆ DNR 3 .}

Takayuki Kihara The inner structures of Turing upward closures

Example

The Dirichlet function χ Q ( x ) = lim _n lim _k cos ^2k ( n !π x ) is

Weihrauch reducible to Σ ⁰

2 -LEM, since Q is Σ ⁰

2 ^{in R .}

χ Q is well-known as an example of Baire class 2, but not 1 function.

Remark

Every ( ≤ _{W Σ} ⁰

2 -DNE)-function is ∆ ⁰

2 -measurable;

hence, it is of Baire class 1 ( = Σ ⁰

2 -measurable).

Not every ( ≤ _W Σ ⁰

2 -LEM)-function is of Baire class 1.

Nonuniform Computability

Consequence

The notion “ ≤ _W constructive principle” develops a new

perspective on classification of discontinuity of functions;

This viewpoint is different from the hierarchy of

Borel measurable / Baire class functions.

Takayuki Kihara The inner structures of Turing upward closures

Consequence

The notion “ ≤ _W constructive principle” develops a new

perspective on classification of discontinuity of functions;

This viewpoint is different from the hierarchy of

Borel measurable / Baire class functions.

This viewpoint also develops a new perspective on

subclasses of Σ ⁰

2 measurable / Baire class 1 functions;

This viewpoint is quite different from

known transfinite hierarchies {B

}

of Baire 1 functions

such as oscillation / convergence / separation rank

(Kechris/Louveau 1990)

Nonuniform Computability

Consequence

The notion “ ≤ _W constructive principle” develops a new

perspective on classification of discontinuity of functions;

This viewpoint is different from the hierarchy of

Borel measurable / Baire class functions.

This viewpoint also develops a new perspective on

subclasses of Σ ⁰

2 measurable / Baire class 1 functions;

This viewpoint is quite different from

known transfinite hierarchies {B

}

of Baire 1 functions

such as oscillation / convergence / separation rank

(Kechris/Louveau 1990)

Hence, the study of Constructive Mathematics can be useful

even on Real Analysis within ZFC based on classical logic!

Takayuki Kihara The inner structures of Turing upward closures

Question (ZFC)

1

_{(≤ cW Σ} ⁰

2 ^{-DNE ) = ∆}

0

2 -measurable?

2

Which semi-constructive principle capture the Baire class 1

functions?

Nonuniform Computability

Kojiro Higuchi, and Takayuki Kihara, Inside the Muchnik

degrees: discontinuity, learnability, and constructivism, in

preparation, 106 pages.

Thank you for your attention!

Takayuki Kihara The inner structures of Turing upward closures