これを実時間の非可逆性に求めるのは釈然としない。なぜならそれは検証ができそうにないし、可逆な系内で構築した計算機によりどんな法則の空間であれエミュレート可能だからである。
そこで、可逆で決定的な系の内部における観測者がなぜある種の現象を、その逆の現象より頻繁に見かけるのかについて直感的な説明を試みる。

経験について

まず、見るからに可逆な現象というのが存在する。たとえば複数のビリヤードの球が動いているという状態と、それぞれの速度が逆転していて逆方向に動いているというのはどちらも同じくありうる。

因果関係すなわち時間の方向を認識させるのは往々にして、運動の質が変わる、特に静止する過程である。このとき運動エネルギーは最終的に熱に変換されるが、その逆、つまり温度が下がって突然物体が動き出すというようなことはあまり経験しないのである。これはなぜか？

この先では、イメージしやすい熱の拡散について、分子の振動を格子状に配置された剛体球がバネで接続されているモデルを使って考えてみる。

認識について

「高い温度の物体と低い温度の物体を接触させると、どちらも同じ中間の温度になるが、その逆は起きない。」というような経験が発生する構造を考えてみる。

まずこの経験には、次の三つの要件(a)が必要である。

「対象」同士、そして「観測者」にあまり結合がなく、別々の物体として、異なる特性を持ちうること
「観測者」がその内部で情報の記憶・比較を行えること
「観測者」が対象にあまり影響を与えずに対象の情報を取得できること(認識)

これにモデルから発生する次の三つの要件(b)を合わせて考える。

「温度」というのは多数の要素の振動の大きさの*1平均値である
「対象」の内部では、各要素の振動の情報は高速に近傍とやりとりされ、巨視的にはエネルギの保存される拡散とある確率分布に従う振動を示す
「観測者」を構成する要素は「対象」よりも大きいので、長時間保持される情報量はある瞬間の対象の情報量より非常に少ないこと

これらを踏まえて、接触と認識がどういう現象なのか考える。

接触

接触はそれぞれの側の要素が各々結合されることとすると、a.1とb.2より非常に多くの場合については各物体の振動は全くインコヒーレントで、通常通りの拡散を示す。一方、これを逆転させた過程というのは、二物体から互いに伝搬していく波が干渉して一つの側では大きい振幅を、もうひとつの側では小さい振幅を作り出す状況である。このような場合というのは全体の場合の数に比べると、要素数Nの場合指数関数的に減少する。

認識

「観測者」がb.1でいう温度をa.3のように認識する過程としては、小さい物体(巨視的現象を生じさせるにたる要素数を持つ)を「対象」に接触させた後、「観測者」内部の何らかのフィードバック系により保持と演算を行うことが考えられる。詳細には立ち入らないが、重要なのはb.3より、物体の内部の位相は「観測者」には分からないということである。このため、前節で述べた場合の数の違いは「観測者」には確率として認識されるのである。

主体の種類

「観測者」の性質というのは「対象」とのスケールの違いによって生じる。先の説明は「観測者」が「対象」と同スケールで疎結合の場合に相当する。同スケールで密結合の場合、単に物体の部分となる。また、スケールが異なり密結合の場合というのはエミュレーションの内外に対応する。これでこのモデルを考える「観測者」とその内側の「観測者」の階層が定義されると同時に、それぞれの層の質的な類似性も内包することができる。

*1:二乗の

2011-07-18

連続系と計算機のちょっと近い関係

はじめに

非常に多くの物理現象は場の相互作用によってよく表されます。そして、その相互作用は絶対座標に依存しない局所的な時間発展を示す偏微分方程式で表されることになります。これらの経験的あるいは解析的な簡略化として、何らかの離散化が行われます。*1工学というのはこれらの簡略化の上に成り立っているわけです。

一方それとは全く異なる方向性として、知性によるもの、つまり概念のシンボル化と操作に基づく体系があります。近代の数学や計算機科学が挙げられますが、前者はともかく後者は物理的実体として実装される必要があって、それは前述の方法によって成されます。

さてここで気になるのは、(チューリング完全な)計算というのは本質的に複雑なプロセスであって*2、それは簡略化とは相容れないということです。つまり、モデル化により一度失われた複雑さをどこで取り戻すかというのが問題になります。

そして現在の状況はというと、できるだけ高速な信号伝送と論理演算を実現し、時間は同期信号で離散化してしまって有限状態機械を構築するということをしているわけです。つまり物理系の複雑性は命題論理に残るのみで、実際の空間と時間は捨象されてしまいます。

時間や空間のような重要な要素を捨ててしまわずに、計算を行う方法としてはセルオートマトン(CA)が挙げられます。これは座標の離散化は行うものの、時間発展に近くの状態しか使わないという点で、「広さ」が維持されていると言えるでしょう*3 *4

しかし、このように物理的な系により近いはずのCAですが、実際にそれを再現するような連続な系を構成した例は見当たらないようです。

そこで、今回はその中でも特に簡単な、一次元の基本セルオートマトン(ECA)*5を再現することにしました。ECAは単純なものの、ルール110と呼ばれている遷移規則を用いるとチューリング完全になることが証明されています*6。

以下ではその具体的な方法について述べます。

*1:線形化はとりうる状態のパターン(つまり基底)の離散化と捉えられるでしょう

*2:digital physicsの立場を取るならばそれより高度な計算は不可能

*3:一見すると時刻は無限に速い信号による同期が必要ですが、これは機械的に非同期なモデルに変換することができます

*4: L. Nehaniv, Self-Reproduction in Asynchronous Cellular Automata, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.2073

*5: http://en.wikipedia.org/wiki/Elementary_cellular_automaton

*6:M. Cook, Universality in Elementary Cellular Automata, http://www.complex-systems.com/Archive/hierarchy/abstract.cgi?vol=15&iss=1&art=01

2011-07-10

ムーア近傍とノイマン近傍のセルオートマトンの相互変換

いわゆる二次元セルオートマトンで用いられる格子として、4つの近傍を持つノイマン近傍と8つの近傍を持つムーア近傍が有名ですが、状態や遷移関数を操作して、同じ「振る舞い」を維持しつつそれらを互いに変換できるか考えてみました。

2011-05-31

λ計算の乱択評価

さて、いわゆる関数型言語の基礎となっているλ計算ですが、一部の言語(eg. Haskell)では厳しく副作用を禁止することでパワフルでありながら参照透過性を維持し、非正格な評価を可能にしています。*1

こうするとうまく評価戦略を選べば*2、λ抽象でない正規形を持つ式は必ず有限時間で評価できて、無限データ構造が使えたりして大変嬉しい訳です。しかし、このような遅延評価を行う言語にはスペースリークの問題があって、例えばfoldl (+) 0 [1..n]等がO(n)のメモリを消費してしまったりします。大量のデータを扱うようなアプリケーションではこれは非常に深刻な問題で、「一行コード追加したらメモリ使いすぎで動かなくなった」みたいなことが発生します。

そこでこのような問題を回避できる(かもしれない)評価戦略として、ランダムにひとつapplicationを選んできてβ簡約することを繰り返す手順を考えてみます。大体の場合うまく行きそうな気がしますが、無限に成長する二分木のようなものがあると、どんどん役に立たない項を選ぶ確率が増えて収束しない場合がありえます。

つまり実際的にはlim_{t->∞}P(E-> ...t... ->NF)>0じゃなくて、lim_{t->∞}P(E-> ...t... ->NF)=1になって欲しいわけですね。無限に大きくなり得る構造を書くとき、それは有限で打ち切られることを期待しているわけですが、そうでなくても積極的に実行して欲しくないなぁというλにはフラグをつけられるような仕組みを考えてみましょう。

そして

フラグの付いてないλがあればランダムにβ簡約
なければ正規形 or 一番外側をβ簡約

なんとなくデフォルトで正格でlazinessを明示的に指定する方法(eg. OCaml)と似ている気がしますが、こっちは何も指定しなくても動く(可能性は0ではない)し、消費メモリが少ない時は全部outermost reductionで、増えてきたら先程の戦略に切り替える等、いろいろいじればちょうどいい感じになるパラメータがあるかもしれません。

どうなんでしょう？

*1:参照透過ならconfluenceがあるので評価順序の制御を隠せる

*2:例えばoutermost reduction