全脳アーキテクチャ勉強会

アナログ計算と計算可能性
平成29年5月9日
河村彰星（東京大学総合文化研究科）
http://www.graco.c.u-tokyo.ac.jp/~kawamura/まず通常の（デジタル）計算理論の考え方について計算の理論
計算 によって何ができるか・できないか決められた手順に従った情報処理（アルゴリズム）
計算のしくみや 使える時間や空間（記憶領域）の量に制約計算機の歴史とともに発展
1930
50
7090
2016

計算可能性

K. Gödel, A. Church, A. Turing,
S. Kleene, E. Post

計算量（時間・空間の制限）

多項式時間

M. Blum, J. Hartmanis
S. Cook, L. Levin, R. Karp

現実の計算機の仕組に特化した議論ではなくむしろ情報処理・知能の一般的な限界を理解したい定義
チューリング機械は次のものにより指定される• 有限個の状態の集合 𝑄 但し次のものが定まっている• 始状態 𝑞始 ∈ 𝑄
離散的な動作• 受理状態の集合
𝑄受理 ⊆ 𝑄• 有限個の文字の集合 𝛴「状態○で記号△を読むと次の時刻にはこれと空白文字
␣ を含む有限個の文字の集合 𝛤• 遷移規則 𝛿:状態と読取り位置を●に変えて
𝑄 × 𝛤 → 𝑄 × 𝛤 × ㊧, ㊨ ∪ 止
記号▲を書込む」という形の規則
初め機械は始状態
𝑞始 にありテープ上に与えられた文字列 𝑥 ∈ 𝛴 ∗ の左端から始めて次のこと（遷移）を繰返す
記号・状態・規則は有限個
状態 𝑞 ∈ 𝑄 で文字 𝜎 を読むと 𝛿 𝑞, 𝜎 が• 「止」なら 停止する
• 𝑞 ′ , 𝜎 ′ , 𝑑 なら状態を 𝑞 ′ にし 𝜎 ′ を書込み 𝑑 の向きに一歩進む
𝑄受理 の状態で停止したら機械は 𝑥 を受理したという

何故「多項式以内か否か」が重要か
入力が大きくなると手間が大違い
入力長𝑛 = 103050100

1000

1万100万

1億𝑛

1秒以内

1秒以内

1秒以内1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

𝑛

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒以内

1秒

2分

𝑛2

1秒以内

1秒以内

1秒以内

1秒以内

1秒

2分

12日

3百年

𝑛3

1秒以内

1秒以内

1秒以内

1秒

17分

12日

3万年 3百億年

2𝑛

1秒以内

18分

36年

4京年

𝑛!

4秒 8百京年

1秒に1000000回の処理ができるとしたときにかかる時間

多項式
時
間
指数時
間

指数個（以上）の組合せから何かを探す場面は多い（組合せ爆発）問題 与えられた正整数（十進法で 𝑛 桁）が素数か判定
それ未満の数（10𝑛 個ほどある）で割り切れるか全部調べれば判る
それよりも劇的に速く 𝑛 の多項式時間で解く方法が見つかった
AKS素数判定法（2002）

問題 与えられたグラフ（頂点 𝑛 個）がハミルトン閉路をもつか判定
頂点の並べ方（𝑛! 個ある）を全部調べれば判る𝑛 の多項式時間で解く方法があるかどうかは判っていない

計算量𝐑𝐄𝐆（有限状態機械で解ける）

𝐏𝐍𝐏
𝐏𝐒𝐏𝐀𝐂𝐄
チューリング機械で解ける問題の分類（困難さの階層）（時間制限なしで）未解決？

𝐏𝐒𝐏𝐀𝐂𝐄 = 𝐏（異なると予想する人が多い）チャーチ・チューリングのテーゼ
数学的にハッキリした主張

ボンヤリした主張

チューリング機械で解ける ⇔ 「実際に計算できる」
現実の「計算」に出て来そうな手順は確かにチューリング機械で実現できる（経験上）
他の色々なやり方で定義された計算可能性の概念とも一致
一般再帰函数、ラムダ計算、…

チューリングの論文
Turing, A.M. (1936). "On Computable Numbers, with anApplication to the Entscheidungsproblem". Proceedings ofthe London Mathematical Society 2, 42: 230–265.
あらゆる処理手順がこの機械の動きとして書けそうな理由を第9節で論じているチューリング機械が計算という行為全般を捉えていると思える理由記号は有限個と考えてよかろう

無限個使ったら区別できなくなるから大きな数値を一記号と考えるとやはり一瞬では区別できない「計算者」の状態も有限としてよかろう

一度に読み書きするのは一字だけとしてよかろう計算ってデジタル・離散的なものだけなの？

「強いチャーチ・チューリングのテーゼ」
チューリング機械で解ける ⇔ 「実際に計算できる」
どんな物理現象を使っても？

NO

YES

チューリング機械ではできない計算ができる
どんな物理現象もチューリング機械で高速に計算（予測）できる計算効率についても？

すごい！

？？？
すごい！

アナログとデジタル
実数値を表現するためにアナログ 物理的な量をそのまま用いる

時刻⇔針の位置デジタル 何らかの離散値に切り捨て

デジタル表現の特徴
予め決められた離散的な値しか表せない保存・複製・誤り訂正などが容易「アナログのままで計算すればよいのでは？」アナログ計算機

微分解析機（Differential Analyzer）
Creative Commons Attribution 3.0 Unported
https://commons.wikimedia.org/wiki/File:Harmonic_analyser_disc_and_sphere.jpg

微分方程式を解くアナログ計算機
加算機・乗算器・積分器などを適当に接続
1870年代にジェームズ＆ウィリアム・トムソンが構想1930年頃に実現 1950年代まで使われる

積分器の原理の例∫ 𝑓 d𝑥J・トムソンの論文（1876）より

汎用アナログ計算機（GPAC）
微分解析機の数理モデル（シャノン 1941）

例一方 実数をデジタルに扱うとは……？

数値への操作「四則演算・ビット演算は単位時間」？
定理［PS76, S79］
整数の「加算」「乗算」「指定ビットの取得」を許すと多項式時間でも PSPACE の問題がすべて解ける
𝑥1 = 10（二進数）
𝑥2 = 𝑥1 ∗ 𝑥1

100𝑥3 = 𝑥2 ∗ 𝑥2𝑥4 = 𝑥3 ∗ 𝑥3⋮

10000
100000000

膨大な桁数を並列に利用して計算ができる（詳細略）

一演算を単位時間というのは「現実的」ではない
正確な演算ができるとして有理数の除算と下位ビットとしても同じ[PS76] V. R. Pratt and L. J. Stockmeyer. On the computational complexity of ordinary differential equations. J.
Comput. Syst. Sci. 12, 198-221, 1976.
[S79] A. Schönhage. On the power of random access machines. In Proc. ICALP, 520–529, 1979.

実数の表現整数など→文字列で表示（零型）

実数など→文字列から文字列への函数で表現（一型）

例：

実数 𝑡𝑛𝑡 の 2−𝑛 近似（距離 2−𝑛 以内にある有理数）

我々が扱いたいのは「二型」の計算

実函数の計算「 𝑡 が任意の正確さでわかるとき𝑓 𝑡 を任意の正確さで求められるか？ 」

計算可能な函数は連続𝑛𝑡 の 2−𝑛 近似

機械 𝑀𝑚𝑓(𝑡) の 2−𝑚 近似

函数 𝑓: [0, 1] → 𝐑 を計算する機械 𝑀
このように定義される（デジタルな意味での）「多項式時間計算可能」を以下 P で表す
空間
PSPACE𝑚 についての計算と連続性
計算可能な函数は連続𝑥 ≥ 0? を判定する
函数は連続でない（ので計算不能）多値函数による判定
は計算可能
𝜀

動作が不定の範囲あり

定理［BH98］
このような多値函数を比較命令として用いた計算はチューリング機械でも効率的に模倣できる[BH98] V. Brattka and P. Hertling. Feasible real random access machines. J. Complexity 162, 490–526, 1998.

計算と連続性∀ε∃δ

連続入力のδ近似から出力のε近似が決る計算可能

計算できる

多項式時間計算可能などたやすく計算できる

アナログ計算の能力は？

微分方程式
単純な
𝑔: 0, 1 × 𝐑𝑑 → 𝐑
から 複雑なℎ: [0,1] → 𝐑𝑑が生じ得るか？

𝑦𝑔 𝑡, 𝑦1 𝑡

ℎ 0 = 0,ℎ′ 𝑡 = 𝑔 𝑡, ℎ 𝑡定理［K83, K10］
リプシッツ連続な函数 𝑔 が P のとき上記の方程式の解 ℎ はどういう意味か？
• 常に PSPACE である• PSPACE 完全である場合がある
PSPACEの中で最難[K83] K. Ko. On the computational complexity of ordinary differential equations. Inform. Contr. 58, 1983.
[K10] A. Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete.
Comput. Complexity 19, 2010.

帰着
質問

多項式時間

答

𝐵

𝐴
入力

質問

出力

多項式時間

答

𝐵
入力

出力

𝐴

𝐴≤𝐵
「𝐴 は 𝐵 に多項式時間で帰着可能」ℎ が PSPACE 完全とは

PSPACE の任意の問題が ℎ に帰着

微分方程式の計算量（PSPACE完全）

微分方程式の計算量（PSPACE完全）

滑らかな動きのみでPSPACE計算を模倣できる！

入出力は何か？
先述のPSPACE完全性は「方程式を無制限なやりとりで指定できる」ことを前提としていた
𝑦与えられた 𝑡, 𝑦 から
𝑔 𝑡, 𝑦 を求めるのは易しいが与えられた 𝑡 からℎ 𝑡 を求めるのは難しい
ような場合が存在すると判った

𝑔 𝑡, 𝑦1 𝑡

しかし実際に「作れる」物理系は・方程式自体はいっぺんに指定できる比較的単純なもの
・初期値は自由に設定できる…とは一体というものであろう
何なのか？

「単純な」微分方程式とは何だろうか？
それに限定すればすべてが多項式時間に収まるのか？
定理［Pour-El 1974, Rubel 1987, Graça 2004］
適切な仮定を置くと GPACで作れる函数は結局
𝑔 が多項式の場合の解 ℎ となっているような函数のみ
このとき ℎ は P
逆に「P の函数は皆 GPAC で近似できる」という結果もある［Bournezら 2007～13］

定理［MM93など］
𝑔 が解析的函数のとき ℎ は P

𝑓 𝑧 = ෍ 𝑎𝑗 𝑧 𝑗「自然界にあるのは解析函数だけ」？

𝑗∈𝐍[MM93] N. T. Müller and B. Moiske. Solving initial value problems in polynomial time. Proc. JAIIO-PANEL
283–293, 1993.

「単純な」微分方程式とは何だろうか？
それに限定すればすべてが多項式時間に収まるのか？
定理［Pour-El 1974, Rubel 1987, Graça 2004］
適切な仮定を置くと GPACで作れる函数は結局𝑔 が多項式の場合の解 ℎ となっているような函数のみ
このとき ℎ は互いに引力を及ぼし合う三点の運動P
逆に「P の函数は皆 GPAC で近似できる」という結果もある［Bournezら2007～13］（衝突など特異点もあり得る）

定理［MM93など］𝑥ሷ = − ෍ 𝑚 ⋅ 𝑥𝑖 − 𝑥𝑗𝑖
𝑗3𝑔 が解析的函数のとき ℎ は𝑗≠𝑖P𝑥𝑖 − 𝑥𝑗

定理［KTZ17］三体問題の或る特殊な場合について与えられた初期値から指定時刻での値を求める問題は初期値を単位立方体から一様に選ぶとき平均計算量は P[KTZ17] A. Kawamura, H. Thies, and M. Ziegler. Average-case complexity for the n-body problem. Proc.
CCA, 2017.

微分方程式の解の存在と計算量ℎ 0 = 0,ℎ′(𝑡) = 𝑔 𝑡, ℎ 𝑡

コーシー・ペアノの定理

コーシー・リプシッツの定理

コーシー・コワレフスカヤの定理

任意の 𝑔 に対し解 ℎ は（原点の近くで）存在

リプシッツ連続な 𝑔 に対し解 ℎ が存在

解析的な 𝑔 に対し解析的な解 ℎ が存在

数学の様々な存在定理を精密化（どの情報からどの情報が決るのか）

コーシー・ペアノの定理（の不成立）＠計算可能［PR79］

数値計算の問題の難しさを計算可能性の視点から分類
コーシー・リプシッツの定理

𝑔 ↦ ℎ は表現法𝛿func の下で計算不可能

＠PSPACE𝑔 ↦ ℎは表現法𝛿func+Lの下でPSPACE

コーシー・コワレフスカヤ＠P𝑔 ↦ ℎは表現𝛿an の下でP

http://cca-net.de/Computability and Complexity in Analysis[PR79] M. B. Pour-El and I. Richards. A computable ordinary differential equation which possesses nocomputable solution. Ann. Math. Log. 17, 1979.

𝑓𝜀

ノイズと予測可能性

𝑓𝜀𝑓𝜀𝜀 ノイズ⋯𝜀 ノイズ

𝑋𝑋

𝑋
エルゴード
定常分布

計算可能距離空間上の離散力学系 𝑓: 𝑋 → 𝑋

定理［GHR11］
𝑓 が P であっても定常分布は一般には計算不能∵ チューリング機械を模倣できる
その挙動が予測できたとすると停止問題が解けてしまう

定理［BGR12］
𝑓 が P であり毎回一定量のノイズがあると・PSPACE
・更に 𝑓 も雑音も解析的ならば P

定常分布は[GHR11] S. Galatolo, M. Hoyrup, and C. Rojas. Dynamics and abstract computability: Computing invariant
measures. Discrete and Continuous Dynamical Systems 29, 193-212, 2011.
[BGR12] M. Braverman, A. Grigo, and C. Rojas. Noise vs computational intractability in dynamics. Proc. ITCS,
128-141, 2012.

まとめ

スライド・論文へのリンク
http://www.graco.c.u-tokyo.ac.jp/~kawamura/t/wbai/

計算理論の目標 「何が（短時間で）計算できるのか」
実数を扱う計算では特に如何なる入出力・表現法・プロトコルで情報をやりとりする話なのか 明確にした上で論ずることが重要
資源や精度の制約をきちんと考えると古典的計算モデルを大きく超えるわけではなさそうとはいえ その「根本的理由」はデジタル計算ほどには明らかでない計算の限界（「NP完全・PSPACE完全問題は簡単に解けないはず」）は物理的世界の情報処理をも支配する原理といえる？［A05］より精密に理解したい[A05] S. Aaronson. NP-complete Problems and Physical Reality. SIGACT News Complexity Theory Column,
2005.