ファイル置き場 Sendai Logic Homepage ihara

導入 主結果

アルゴリズム学習理論に基づく動的証明モデルと不連続関

数の階層

木原 貴行

東北大学大学院理学研究科数学専攻

2011^年5^月13^日

導入

主結果

位相空間と学習理論

動的証明モデル

不連続関数の計算可能性

計算可能解析学の基本定理

任意の位相空間上の計算可能関数は連続である．

例

ステップ関数や床関数はユークリッド位相では計算不可能である．

不連続関数の計算可能性 八杉満利子

上の例のような簡単な関数が計算不可能なのは奇妙である．

アプローチ 位相を変えて，ステップ関数や床関数を計算 する．

アプローチ ステップ関数や床関数は学習可能である．

導入

主結果

位相空間と学習理論

動的証明モデル

不連続関数の計算可能性

計算可能解析学の基本定理

任意の位相空間上の計算可能関数は連続である．

例

ステップ関数や床関数はユークリッド位相では計算不可能である．

不連続関数の計算可能性₍八杉満利子_etc.)

上の例のような簡単な関数が計算不可能なのは奇妙である．

アプローチ 位相を変えて，ステップ関数や床関数を計算 する．

アプローチ ステップ関数や床関数は学習可能である．

導入

主結果

位相空間と学習理論

動的証明モデル

不連続関数の計算可能性

計算可能解析学の基本定理

任意の位相空間上の計算可能関数は連続である．

例

ステップ関数や床関数はユークリッド位相では計算不可能である．

不連続関数の計算可能性₍八杉満利子_etc.)

上の例のような簡単な関数が計算不可能なのは奇妙である． (^{アプローチ}1)位相を変えて，ステップ関数や床関数を計算 する．

アプローチ ステップ関数や床関数は学習可能である．

導入

主結果

位相空間と学習理論

動的証明モデル

不連続関数の計算可能性

計算可能解析学の基本定理

任意の位相空間上の計算可能関数は連続である．

例

ステップ関数や床関数はユークリッド位相では計算不可能である．

不連続関数の計算可能性₍八杉満利子_etc.)

上の例のような簡単な関数が計算不可能なのは奇妙である． (^{アプローチ}1)位相を変えて，ステップ関数や床関数を計算 する．

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！

学習者「」

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！ 2, . . .

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！ 2, . . . 学習者「偶数と予想」

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！ 2, 3, . . .

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！ 2, 3, . . . 学習者「素数と予想」

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！

2, 3, 5, . . .

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！

2, 3, 5, 8, . . . 学習者「… … 」

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！

2, 3, 5, 8, . . .

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

アルゴリズム学習の例：_Goldの極限同定₍₁₉₆₅₎

学習者の目的は，与えられた無限列の規則を説明する法則を 見つけることである．

ただし，学習者（人，動物，機械_etc.）は有限的なので，無 限列のうちの有限部分しか参照することができない． 学習者とは関数：有限列_7→法則．

法則は何らかの言葉で記述されるとし，自然数でコードする．

例

次の数列の規則を見つけよ！

2, 3, 5, 8, 13, . . . 学習者「フィボナッチ数列と予想」

導入

主結果

位相空間と学習理論

動的証明モデル

学習可能とは何か？

Gold^{の極限同定}(1965)

学習者とは，部分計算可能関数_{Ψ : N}^<N_{→ N}である． Φe ^{を法則eが表す部分関数}Φe : N → N^とする． 学習者_Ψが無限列_{f ∈ N}

N

を同定するとは，_Φlim

tΨ(f↾t) ^=f

を満たすことである．

実際の極限同定では，N上の部分関数の同定を扱うことが多いが， ここでは簡略化のため，全域関数_{f ∈ N}

N

しか扱わない．

導入

主結果

位相空間と学習理論

動的証明モデル

ベール空間 N

N

上の学習可能関数

X,Y ⊆ N^{Nとする．}f :X →Y^{が学習可能とは，} (∃Ψ)(∀x ∈X)f(x) = Φ_{limtΨ(x↾t)}(x).

このような_Ψを_fの学習者と呼ぶ．

1 _{f : X →Yの学習者Ψが心変わり有界とは，}

(∃b)(∀x ∈ X) #{t ∈ N: Ψ(x ↾t +1) , Ψ(x ↾t)} < b.

2 _{f : X →Yの学習者Ψが誤り有界とは，}

(∃b)(∀x ∈ X) #{Ψ(x ↾t) :t ∈ N} <b.

計算可能 心変わり有界学習可能

      誤り有界学習可能 学習可能

ステップ関数 床関数 心変わり有界学習可能 計算可能

導入

主結果

位相空間と学習理論

動的証明モデル

ベール空間 N

N

上の学習可能関数

X,Y ⊆ N^{Nとする．}f :X →Y^{が学習可能とは，} (∃Ψ)(∀x ∈X)f(x) = Φ_{limtΨ(x↾t)}(x).

このような_Ψを_fの学習者と呼ぶ．

1 _{f : X →Yの学習者Ψが心変わり有界とは，}

(∃b)(∀x ∈ X) #{t ∈ N: Ψ(x ↾t +1) , Ψ(x ↾t)} < b.

2 _{f : X →Yの学習者Ψが誤り有界とは，}

(∃b)(∀x ∈ X) #{Ψ(x ↾t) :t ∈ N} <b.

計算可能 心変わり有界学習可能

      誤り有界学習可能 学習可能

ステップ関数 床関数 心変わり有界学習可能 計算可能

導入

主結果

位相空間と学習理論

動的証明モデル

ベール空間 N

N

上の学習可能関数

X,Y ⊆ N^{Nとする．}f :X →Y^{が学習可能とは，} (∃Ψ)(∀x ∈X)f(x) = Φ_{limtΨ(x↾t)}(x).

このような_Ψを_fの学習者と呼ぶ．

1 _{f : X →Yの学習者Ψが心変わり有界とは，}

(∃b)(∀x ∈ X) #{t ∈ N: Ψ(x ↾t +1) , Ψ(x ↾t)} < b.

2 _{f : X →Yの学習者Ψが誤り有界とは，}

(∃b)(∀x ∈ X) #{Ψ(x ↾t) :t ∈ N} <b.

計算可能 _⊆ 心変わり有界学習可能

     _⊆ 誤り有界学習可能 _⊆ 学習可能

ステップ関数_,床関数_∈ 心変わり有界学習可能 ₋ 計算可能

導入

主結果

位相空間と学習理論

動的証明モデル

Medvedev

^の意味論

直観主義命題計算の意味論

Kolmogorov (1932)は命題を問題と解釈することにより，直

観主義命題計算の意味論を与えるようと試みた．

Medvedev (1955)^はKolmogorovのアイデアに基づき，次の 命題計算を考案した．

の意味論

各命題 は集合 と解釈される．

が証明可能とは， が計算可能な要素を持つことである．

導入

主結果

位相空間と学習理論

動的証明モデル

Medvedev

^の意味論

直観主義命題計算の意味論

Kolmogorov (1932)は命題を問題と解釈することにより，直

観主義命題計算の意味論を与えるようと試みた．

Medvedev (1955)^はKolmogorovのアイデアに基づき，次の 命題計算を考案した．

Medvedev^の意味論(1955) 各命題_Pは集合_{P ⊆ N}

N

と解釈される．

P^{が証明可能とは，}P が計算可能な要素を持つことである．

導入

主結果

位相空間と学習理論

動的証明モデル

Medvedev^の意味論(1955)

証明者が命題_P を証明するとき_:

無限の長さのテープが与えられている．

導入

主結果

位相空間と学習理論

動的証明モデル

Medvedev^の意味論(1955)

証明者は，各時刻で証明を₁文字書き加える． 証明とは，証明者によって記述される無限列_{α ∈ N}

N

である．

導入

主結果

位相空間と学習理論

動的証明モデル

Medvedev^の意味論(1955) 命題とは，集合_{P ⊆ N}

N

である．

命題_P を証明するとは，_P の要素を記述する手続き₍法則・

導入

主結果

位相空間と学習理論

動的証明モデル

… … このような動的な意味論は，直観主義よりもむしろ学習理論 に基づく論理体系と相性が良さそう？

導入

主結果

位相空間と学習理論

動的証明モデル

極限計算可能数学

極限計算可能数学₍林晋etc. 2001-)

1 _(林2001?) 学習理論に基づく半構成的数学の体系

極限計算可能数学(Limit Computable Mathematics)^を導入

2 _{(赤間-Berardi-林}-Kohlenbach 2004)^{直観主義算術上の弱い} 排中律の算術的階層の研究．

3 _{(Berardi-山形2008)}極限計算可能数学に対応するシーケント

計算を導入．

今回のお話

『 の意味論』と『林の極限計算可能数学』を混ぜ合わ せてみると… … ある種の位相空間上の不連続関数の学習可能性に 関するちょっと面白い現象が起こるかも？

導入

主結果

位相空間と学習理論

動的証明モデル

極限計算可能数学

極限計算可能数学₍林晋etc. 2001-)

1 _(林2001?) 学習理論に基づく半構成的数学の体系

極限計算可能数学(Limit Computable Mathematics)^を導入

2 _{(赤間-Berardi-林}-Kohlenbach 2004)^{直観主義算術上の弱い} 排中律の算術的階層の研究．

3 _{(Berardi-山形2008)}極限計算可能数学に対応するシーケント

計算を導入．

今回のお話

『_Medvedevの意味論』と『林の極限計算可能数学』を混ぜ合わ せてみると… … ある種の位相空間上の不連続関数の学習可能性に 関するちょっと面白い現象が起こるかも？

導入

主結果

位相空間と学習理論

動的証明モデル

今回は論理和_(∨)に注目しよう！

論理和の動的な証明モデル の意味論 を考えると 何が嬉しい？

直和や和集合を越えて，『複雑に絡み合った和』の概念を導入 できる！

この複雑に絡み合った和を，どのような不連続関数でなら

『解きほぐす』ことが出来るだろうか？

導入

主結果

位相空間と学習理論

動的証明モデル

今回は論理和_(∨)に注目しよう！

論理和の動的な証明モデル_(Medvedevの意味論₎を考えると 何が嬉しい？

直和や和集合を越えて，『複雑に絡み合った和』の概念を導入 できる！

この複雑に絡み合った和を，どのような不連続関数でなら

『解きほぐす』ことが出来るだろうか？

導入

主結果

位相空間と学習理論

動的証明モデル

今回は論理和_(∨)に注目しよう！

論理和の動的な証明モデル_(Medvedevの意味論₎を考えると 何が嬉しい？

直和や和集合を越えて，『複雑に絡み合った和』の概念を導入 できる！

この複雑に絡み合った和を，どのような不連続関数でなら

『解きほぐす』ことが出来るだろうか？

導入

主結果

位相空間と学習理論

動的証明モデル

今回は論理和_(∨)に注目しよう！

論理和の動的な証明モデル_(Medvedevの意味論₎を考えると 何が嬉しい？

直和や和集合を越えて，『複雑に絡み合った和』の概念を導入 できる！

この複雑に絡み合った和を，どのような不連続関数でなら

『解きほぐす』ことが出来るだろうか？

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_I

証明者_Ψが_{P ∨Q}を証明するとき_:

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_I

各時刻で，_Ψはどちらかの_{X ∈ {P,Q}}について『_X は真だ』 と宣言し，文字_X を紙_に書き込む．

各時刻で， はテープ に一文字 を書き加える．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_I

各時刻で，_Ψはどちらかの_{X ∈ {P,Q}}について『_X は真だ』

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_I

最終的に，ある文字_Xが_に書かれている． 最終的に，ある無限語_f が_Λに書かれている． P ∨Q^{の証明成功！} ⇐⇒ f ∈ X.

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_{I (}直観主義₎

Ψ X ∈ {P,Q}

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_{I (}極限計算可能数学₎

LCM^証明者Ψは有限回だけ宣言を変えることができる．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_{I (}古典₎

古典証明者_Ψはそもそもどちらが真か宣言をしない．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

1 _{直観主義1-論理和⟦P0∨P1⟧}¹

Int^:

{f ⊕g ∈ N^N : (∃i <2)((∀n)f(n) =i &g ∈ P_i)}.

2 _{LCM 1-論理和⟦P0∨P1⟧}¹

LCM^:

{f ⊕g ∈ N^N: (∃i < 2)((∀^∞n)f(n) =i &g ∈P_i)}.

3 _{古典1-論理和⟦P}

0^∨P1^⟧1_CL^:

{f ⊕g ∈ N^N: (∃i <2)g ∈P_i}.

注意

⟦· ∨ ·⟧¹

Int^{は直和⊕と大体同じ．}

⟦· ∨ ·⟧¹

Cls^は和集合

∪

と大体同じ．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_II

証明者_Ψが_{P ∨Q}を証明するとき_:

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_II

最終的に_fP,fQがそれぞれ_ΛP,ΛQに書かれている． P ∨Q^{に証明成功} ⇐⇒ f_P ∈ ΛP^またはfQ ^∈ ΛQ^.

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_{II (}直観主義₎

Ψ X ∈ {P,Q} ΛX

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_{II (}極限計算可能数学₎

LCM^証明者Ψは書き込むテープを有限回だけ変えることができ る．つまり，最終的に一方のテープ_ΛXには有限語が書かれ，他 方のテープ_ΛYには無限語が書かれる．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

動的証明モデル_{II (}古典₎

Ψ ΛX ^{n ∈ N}

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

For f ∈(2× N)^N, and i <2, zⁱ

n ⁼the n-th least element of{m: (f(m))₀ =i. pr_i(f)(n) = (f(z_nⁱ))₁if z_nⁱ ↓.

mc(f) = #{n : (f(n))0 ^, (f(n+1))0^}.

は，時刻 で 番目のテープに を書き加える は最終的に 番目のテープに書かれる語．

は書き込みテープを変更する回数．

のとき， かつ

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

For f ∈(2× N)^N, and i <2, zⁱ

n ⁼the n-th least element of{m: (f(m))₀ =i. pr_i(f)(n) = (f(z_nⁱ))₁if z_nⁱ ↓.

mc(f) = #{n : (f(n))0 ^, (f(n+1))0^}.

f(s) = ⟨i,k⟩^は，時刻s^でi^{番目のテープに}k^{を書き加える} pr_i(f)^{は最終的に}i番目のテープに書かれる語．

mc(f)は書き込みテープを変更する回数．

のとき， かつ

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

For f ∈(2× N)^N, and i <2, zⁱ

n ⁼the n-th least element of{m: (f(m))₀ =i. pr_i(f)(n) = (f(z_nⁱ))₁if z_nⁱ ↓.

mc(f) = #{n : (f(n))0 ^, (f(n+1))0^}.

f(s) = ⟨i,k⟩^は，時刻s^でi^{番目のテープに}k^{を書き加える} pr_i(f)^{は最終的に}i番目のテープに書かれる語．

mc(f)は書き込みテープを変更する回数．

f = ⟨0,1⟩, ⟨0,9⟩, ⟨1,1⟩, ⟨0,4⟩, ⟨1,3⟩, ⟨0,5⟩, ⟨1,7⟩, ⟨1,0⟩, . . . のとき，_{pr0(f) =1,9,4,5, . . .} かつ_{pr1(f) =1,3,7,0, . . ..}

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

1 _{直観主義2-論理和⟦P}

0^∨P1^⟧2_Int^:

{f ∈ N^N : ((∃i)pr_i(f) ∈P_i) &mc(f) = 0}.

2 _{LCM 2-論理和⟦P}

0^∨P1^⟧2_LCM^:

{f ∈ N^N : ((∃i)pr_i(f) ∈P_i) & mc(f) < ∞}.

3 _{古典2-論理和⟦P0 ∨P1⟧}²

CL^:

{f ∈ N^N : (∃i) pr_i(f) ∈P_i}.

命題

で，ある計算可能関数 が存在することを意味す る．任意の 集合 について，次が成立する．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

1 _{直観主義2-論理和⟦P}

0^∨P1^⟧2_Int^:

{f ∈ N^N : ((∃i)pr_i(f) ∈P_i) &mc(f) = 0}.

2 _{LCM 2-論理和⟦P}

0^∨P1^⟧2_LCM^:

{f ∈ N^N : ((∃i)pr_i(f) ∈P_i) & mc(f) < ∞}.

3 _{古典2-論理和⟦P0 ∨P1⟧}²

CL^:

{f ∈ N^N : (∃i) pr_i(f) ∈P_i}.

命題

X→Y ^{で，ある計算可能関数}f :X →Yが存在することを意味す る．任意の_Π⁰

1^{集合P,Q ⊆2} N

について，次が成立する． P⊕Q↔⟦P ∨Q⟧¹

Int^{↔⟦P ∨Q⟧} 2

Int^{→⟦P ∨Q⟧} 1

LCM^{→⟦P ∨Q⟧} 1 CL

P∪Q↔⟦P ∨Q⟧¹

CL^{→⟦P ∨Q⟧} 2

LCM^{→⟦P ∨Q⟧} 2 CL^.

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

P ⊕Q:⟦P∨Q⟧¹

Int^{や⟦P ∨Q⟧} 2

Int^のこと

P ∪Q: ⟦P ∨Q⟧¹

CL^のこと

P▽Q: ⟦P ∨Q⟧²

LCM^{の心変わり1バージョン}

P▽_limQ:⟦P ∨Q⟧²

LCM^のこと

P gQ: ⟦P ∨Q⟧²

CL^のこと

命題

P,Q ⊆2^NをΠ⁰

1^{集合とする．}

P ⊕Q→P∪Q→P▽Q→P▽ Q→P gQ

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

古典_2-論理和の動的証明過程_{α ∈P gQ}を知っているとき，_αは P^かQの少なくとも一方の証明の情報を含んでいるはず！

Φ_X:^『X が真』だと最初に宣言して，_αから_Xの証明情報を 抜き出そうと試みる部分計算可能関数

このとき，_{P gQ}の分割_A,Bが存在して，

ΦP :A →P ⊕Q^かつΦQ :B →P ⊕Q^{が満たされる．}

定義

とする．

が並行計算可能 の有限分割 が存 在して，各 について が計算可能．

が弱計算可能 の無限分割 が存在 して，各 について が計算可能．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

古典_2-論理和の動的証明過程_{α ∈P gQ}を知っているとき，_αは P^かQの少なくとも一方の証明の情報を含んでいるはず！

Φ_X:^『X が真』だと最初に宣言して，_αから_Xの証明情報を 抜き出そうと試みる部分計算可能関数

このとき，_{P gQ}の分割_A,Bが存在して，

ΦP :A →P ⊕Q^かつΦQ :B →P ⊕Q^{が満たされる．}

定義

X,Y ⊆ N^{Nとする．}

f : X →Y^{が並行計算可能} ⇐⇒ X^{の有限分割}{X_i}_i<b ^が存 在して，各_{i <b} について_{f ↾ Xi}が計算可能．

f : X →Y^{が弱計算可能} ⇐⇒ X^{の無限分割}{X_i}_i∈N^が存在

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

観測

P,Q ⊆ N^{Nとする．}

1 心変わり有界学習可能関数_{f :P ∪Q →P ⊕Q}は存在する．

2 心変わり有界学習可能関数_{f :P▽Q →P ∪Q}は存在する．

3 _{誤り有界学習可能関数f : P▽}

lim^{Q →P▽Qは存在する．}

4 _{並行計算可能関数f :P gQ →P▽limQは存在する．}

主定理

次を満たす 集合 が存在する．

計算可能関数 は存在しない．

計算可能関数 は存在しない．

心変り有界学習可能関数 は存在しない 誤り有界学習可能関数 は存在しない．

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

観測

P,Q ⊆ N^{Nとする．}

1 心変わり有界学習可能関数_{f :P ∪Q →P ⊕Q}は存在する．

2 心変わり有界学習可能関数_{f :P▽Q →P ∪Q}は存在する．

3 _{誤り有界学習可能関数f : P▽}

lim^{Q →P▽Qは存在する．}

4 _{並行計算可能関数f :P gQ →P▽limQは存在する．}

主定理

次を満たす_Π⁰

1^{集合P,Q ⊆2} N

が存在する．

1 _{計算可能関数f : P∪Q →P⊕Qは存在しない．} 2 _{計算可能関数f : P▽Q →P ∪Qは存在しない．}

:

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

P⊕Q

P ∪Q

P▽Q

P▽_limQ

P gQ

id∈FM

,,

YY Y YY Y Y

ΓbM^∈FbM

llYYY YY

YY

ΓM^∈FM

vv

id∈FM

,,

Y YY YY Y Y

Γbl^∈Fbl

llYYY YY

YY

ΓM∈FM

vv

id∈FM

,,

YY Y YY YY

Γbel^∈Fbel

llYYYYYY Y

Γbl^∈Fbl

vv

id∈FM

,,

YY Y YY YY

Γb∈Fb

llYYYYYY Y

Γbel^∈Fbel

vv

Figure:互いに独立な_Π⁰

1^{集合たちP,Q ⊆2} N

の2-論理和モデル

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

記号

▽

| {z }

n個

.

▽

▽

g

| {z }

n^個

.

H

▽

▽

▽

| {z }

n^個

.

g

g

H

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

定理

X,Y ⊆ N^{Nとする．}

1 心変わり有界学習可能関数_{f :X →Y} が存在する

⇐⇒ (∃n)^{計算可能関数}g :X →

▽

2 学習可能関数_{f : X →Y}が存在する

⇐⇒ ^{計算可能関数}g :X →

▽

3 _{並行計算可能関数f :X →Y が存在する}

⇐⇒ (∃n)^{計算可能関数}g :X →

g

4 _{チーム学習可能関数f :X →Y が存在する}

⇐⇒ (∃n)^{計算可能関数}g :X →

H

5 _{弱計算可能関数f :X →Yが存在する}

⇐⇒ ^{計算可能関数}X →

g

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

主定理

P,Q ⊆2^{Nを空でない}Π⁰

1^{集合とする．}

1 _{ある計算可能関数f :P▽P →Pが存在するならば，}

Pは計算可能な要素を持つ．

2 _{ある並行計算可能関数f :}

_▽

Pは計算可能な要素を持つ．

3 _{ある学習可能関数f :}

_▽

_▽

Pは計算可能な要素を持つ．

4 あるチーム学習可能関数_{f :}

_g

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

P

▽

2^P

▽

H

2^P

g

id∈FM

,,

YY Y YY YY Y YY

Γbl∈Fbl

llYYYY YY

YY YY

ΓM^∈FM

vv

id∈FM

,,

YY YY YY Y YY

Γl^∈Fl

llYYYY YYY

YY

Γb^∈Fb

vv

id∈FM

,,

YY YY Y YY YY

Γtl^∈Ftl

llYYYYY YYYY

Γl^∈Fl

vv

id∈FM

,,

Y YY Y YY YY Y

Γw^∈Fw

llYYYY YYY

YY

Γtl^∈Ftl

vv

Figure:計算可能な要素を持たない非空_Π⁰

1^{集合P ⊆2} N

の動的証明モ デル

導入 主結果

論理和による並行計算の階層

動的証明による弱計算の階層

Thank you!