グラフ彩色とパス表現

無向グラフについて、k色のうちいずれかをそれぞれの頂点に割り当てたとき、全ての辺の両端が異なる色ならばそのグラフをk-彩色可能といいます。平面埋め込み可能なグラフは全て4-彩色可能というのが、有名な四色定理です。

さて各頂点がある埋込みの中の位置を表していると考えると、隣接する位置の色が異なる、つまり互いに区別できるという解釈ができます。しかし、図の左上の水色の頂点がふたつの桃色の近傍をもっているように、微小な領域での「向き」を一意に区別することはできません。

そこで、それを可能にする彩色を考えてみると、次のように表現できます。



すべての頂点について、自身とその近傍の色が全て異なる
k色でこの条件を満たせるグラフを、ここでは仮にk-追跡可能と呼ぶことにしましょう(この条件の一般的な名称を知っている方がいたら教えてもらえると嬉しいです)。また、グラフGの彩色、追跡それぞれの最小色数をχ(G)、τ(G)と書くことにします。

さて、k-追跡可能グラフの特徴をいくつか考えてみましょう。

k-彩色可能性との関係

明らかに、k-追跡可能ならばk-彩色可能です。一方その逆は成り立ちません。例えば平面グラフは任意の次数を持ち得てかつχ<=4ですが、最大次数がnのときτ>=n+1である必要があります。一般にτ>=max(χ,n+1)と言えるでしょう。

パスの表現

さてこの命名の由来ですが、k-追跡可能なとき、ある頂点の近傍は{1..k}のいずれかを用いて一意に表現できます。よって長さnの任意のパスは起点となる頂点ひとつと{1..k}^nで表せます。これはグラフ上を移動するエージェントのようなものを考えるときには有用な性質です。なぜなら、局所的にグラフを見ているときに、そのパスの表現に必要な情報量が全体の頂点数、そもそも有限か無限かにも依存しなくなるからです。(有限のτを考えているとき、辺の数=O(頂点数)となります)

格子の構成

さて頂点集合をZ^nとし、マンハッタン距離が1の二点を近傍とする格子Lnを考えてみます。次数はいたるところで2dで、座標の成分の和のパリティによって2-彩色可能です(図左)。τ(Ln)はどうなるでしょうか。

これはまず一次元の直線を考えてみるとよくわかります。各点において右と左そして自分自身を区別するのに最低三色必要で、これを座標に沿って循環的に割り当てていくと全体をカバーできます。個人的には、同期セルオートマタの非同期化( http://jsdo.it/xanxys/ascwlife )の時に、時間を三状態の「位相」で表したことが思い出されます。では、二次元の場合はどうでしょう。この場合は各軸を独立に見てそれぞれに三色を割り当てる、つまり全体では九色使うと3x3の繰り返し要素がつくれます(図右)。

同様に次元が高いLnについても、3^n色使えば充分です。つまり2n+1<=τ<=3^nとなるのですが、3^nより少ない色数で追跡可能になるかどうかはよくわかりません。

備忘録: 「空間」の用法

記事を書いた時点での、筆者のイメージによる空間の使い分け。定義を意識して使っているわけではないが、これらには考えの方向性の違いがある。

物理

  1. 古典的な物理学における解析的な場
  2. 上記に時間をつけ加えたもの
  3. 一部が離散化されたand/or確率的な場
  4. 上記に時間をつけ加えたもの
  5. シミュレーションにおいて、上四つのそれぞれに対応するもの

形而上学

  1. 宇宙全体を内側から見て、時間と空間を独立に考えた時の空間のみ
  2. 宇宙全体を内側から見たとき、我々を含む連結な時空
  3. 宇宙全体を、時間と空間が分離していて、かつ内側と外側の空間が対応している時の外側から見た、内側の空間
  4. 宇宙全体を、時間と空間が分離していない外側から見たときの、内側の時空全て
  5. 必ずしも数学的でない、「もの・こと」のあつまり

数学

  1. 集合
  2. 写像
  3. 距離空間
  4. ベクトル空間
  5. ヒルベルト空間
  6. ユークリッド空間

工学

  1. 量を組み合わせたものから別の量への写像

計算機

  1. 一次元のメモリ
  2. プールとしてのメモリ
  3. 抽象的なストレージ
  4. ネットワークのノードが配置される(物理的あるいは数学的な)場所

認知

  1. 直感的な広さに対応するなにか
  2. 神経系全体として暗黙的に持っている世界のモデル
  3. 上記の真に小さい一部分
  4. 二つ上の、一部の感覚についてのみ(仮想的に)分離したもの
  5. 上記の真に小さい一部分

そのた

  1. なんとなく一般にイメージされる(と思っている)電脳空間
  2. 「電脳コイル」における電脳空間
  3. 上記の実装(まだない)がつくるなにか
  4. 単なる文章上のプレースホルダーで意味がない場合

HTMLのクライアントサイドマークアップ

さて、最近は『電脳コイル規格書』( http://www.xanxys.net/dc/ )というちょっとしたコメンタリを書いていたのですが、10パラグラフ以上あるような文章だとHTMLを完全に手書きするのは見通しも悪く、ちょっと面倒です。

もちろん十分長いものや続き物であれば、wikiのようなCMSを導入したり、ローカルで変換スクリプトを書いたりするのがまっとうな方法でしょうが、前者は明らかに面倒ですし後者も公開用の静的ファイル群とは別に管理する必要があります。

そこで、静的ファイルだけで完結するような方法で、かつjavascriptに対応していないであろう検索エンジンにもそこそこ拾われるような方法が求められます。

そこでちょっとしたスクリプトを書いてみました。

続きを読む

なぜ主観時間は単方向に流れるか？

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

経験について

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

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

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

認識について

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

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

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

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

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

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

接触

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

認識

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

主体の種類

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

*1:二乗の

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

はじめに

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

続きを読む

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

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

続きを読む

λ計算の乱択評価

さて、いわゆる関数型言語の基礎となっているλ計算ですが、一部の言語(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になって欲しいわけですね。無限に大きくなり得る構造を書くとき、それは有限で打ち切られることを期待しているわけですが、そうでなくても積極的に実行して欲しくないなぁというλにはフラグをつけられるような仕組みを考えてみましょう。

そして

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

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

どうなんでしょう？

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

*2:例えばoutermost reduction