自己複製系と意味

ある系の環境からの独立性は、環境の変化に対する安定性で測れます。例えば結晶の成長過程は、結晶がその環境から必要な物質を引っ張ってきて、単位格子が増殖している、とも見れます。しかし温度変化や不純物に敏感で、通常は自己複製系としては扱いません。*1

一方、明確な自己複製系として細胞があり、これはかなり安定、かと思いきや、単にある物質濃度が高いだけで複製が止まったりしますし、生命が結晶とどう違うのかはそんなに明白ではありません。

ここでは生命がなんであるかは脇に置いて、次の定義を満たすものを自己複製系と呼びます。

有限の空間的なパターンであって、環境変化に対して安定で、環境から内部で使用可能なエネルギーを取り出し、時間の経過によりそのパターンを複製するもの。

さて、問題なのは「環境変化」とか「安定」とか「複製する」とか「内部で用いることの出来る」、あたりだと思います。まず、「安定」と「複製」は、どちらもパターンが同一視出来るかに帰着されます。で、「使用可能」というのは、外部から「知ってる」形のエネルギーを取り込み、それで何か内部に変化が起きて、「知らない」形のエネルギーに変換されるという事です。(期待通りの形式で何かが入って、把握できないものが出ていくというのは、情報を捨てているわけです。つまり不可逆計算をしているとも言えます。)

これは一体どういうことでしょうか？私の好きな解釈は、自己複製系は意味境界を作る最小単位である、というものです。

そもそも複製されたパターンが同一であるというのは、その中で行なっている処理が同じであるということです。そして、事前の情報共有は通信の必須要件です。これがあれば環境を介した何らかのプロトコルに従って互いを認識することが可能です。*2

で、この解釈の美しいところは、その「情報」や「処理」がどんな形で物理にエンコードされているのか、それを知らなくてもいい、ということです。実際、知る術はありません。単にこの物質はあのシグナルなのかな〜と見立てることしかできません。*3

つまり、ある自己複製系は集団として、意味的に閉じた系であるという事です。

これが、もし量産された無線情報機器だとしましょう。もちろん、互いを認識できます。が、それは人間が決めたプロトコルに従っているのであって、人間は全てのレイヤーの詳細を知っています。だから、その機器には互いが本当に同質のものかはわからないのです。いや、同質であると「信じて」いるのですが、実際にはそうでないものを作れるという事です。

つまり、情報ではなく、情報の表現形式そのものを隠蔽することが、意味の境界をつくります。で、自己複製はそれを成し遂げる手段です。

安定性

さて、とりあえず自己複製系の定義をしたので、今度はその安定性について。

複製・処理のメカニズムはなんであれ、そのスケールに依存します。複製するたびに大きさが1%増えていたら、いずれはそのメカニズムが働く閾値を超えてしまうでしょう。だから、キャリブレートする必要があるのですが、その基準をどうするかというのが安定性になります。

で、細胞は原子が文字通りatomicであることに依存しています。が、そうでなくともスケールが均一に変わるなら、スケール変化に特に敏感なメカニズムを付加して自爆すればいい。が、原子がまるで剛体球のようにそれぞればらばらに変化したらそれもできない。

するとどうなるか？空間には原子の平均大きさというゆらぎができる。しばらくは問題ない。でも人間みたいなのが出てくると、そのうち、別の粒子との関係が場所によって変わってることや、真空中ではそのような量が定義できない、温度のようなものであると気づく。そしてその影響を補正すれば素粒子と呼べて量子力学が・・・

・・・と書いていて、別にatomicityはどうでもいいことに気づきました。

というわけで、安定性は構造のみから決定できるものではなく、他の量と同じく環境の問題として扱えることがわかりました。

*1:とはいえ、まったく引き込みが起きないわけではありません。

*2:それをすることが必須ではありません。

*3:ところで、これって反証可能ではない言説なのでは？

写真内の相互情報量

さて、画像処理では区分的に滑らかであるという仮定をよく用います。これは我々から見た世界が大方はっきりした境界を持つ物体と透明な空気によって成りなっているという(まっとうな)前提から導かれます。で、多くの場合(主にCG)もっとてきとうに、とりあえずbilinear補間使おうとか、Mitchellフィルタかけておこう、となるわけです。

さて、実際の画像はどうなっているのでしょうか？ここでは画像内の全てのピクセルの組み合わせについて相互情報量を計算することで、ある点が近くの別の点にどのぐらい影響を及ぼすか、ということを調べて見ることにします。基底の形に直接対応するわけではありませんが、参考程度にはなるでしょう。

というわけで、前(Scene Completion Using Millions of Photographs)にも使った、flickrから持ってきた風景写真10万枚ほどを次のように処理します。

  1. アスペクト比が1.3から1.4に収まってるものを選ぶ
  2. 40x30に縮小
  3. RGBからL*a*b*に変換後、L*を16階調に量子化
  4. 全てのピクセル対について、16x16でヒストグラム作成

もにょもにょっとすると相互情報量が計算できます。有効な(1の条件を満たす)画像数は62498枚でした。自分自身との相互情報量が最大で、これは高々4bitになります。

(青〜赤 : 0bit〜4bit)
拡大してみると、赤い点があるのが分かります。とはいえほとんど真っ青なので、スケールを変えてみましょう。

(青〜赤 : 0bit〜1bit+)
まず目につくのは上下に帯状に見られる横に長い形です。これは空と地面に対応していると言えるでしょう。で、真ん中のほうは円対称かというとそうでもなく、ちょっと+っぽい形をしています。これはやはり鉛直方向と写真の向きを合わせているからでしょうか？

ちょっと離れてみると、心なしか右のほうが赤っぽいように感じます。これは利き手の偏りと関係があるのでしょうか。今回はflickrから引っ張ってきたのである程度「写真」として、それなりの芸術性が含まれているとは思うのですが、もし無意識に右側(利き手の側?)に物体が来るような姿勢を取るのであればおもしろいことです。

3dプリンタつくりました

さて、3dプリンタつくる宣言*1 してから早1.5ヶ月が経ち、ようやく「これは3dだ！」という感じの物体が印刷できるようになったので報告します。


(モデルはThingiverse*2の3D Knot)

・・・うーん。やけに凸凹してますが紛れもなく結び目に見えますね！

以下ではとりあえずプリンタ本体、この印刷物、今後の方針について、とつらつら書いていこうかと思います。

本体


さて設計のかなりの部分についてはGoogle Docsで公開している*3ので、あらましだけ書きます。基本的に今回の設計の方針は手持ちの部品を有効活用するということなので一万円かかってませんが、再現しようとすると5万円越えると思います。3dプリンタが欲しい人は素直にreprap系のキットや完成品を買うのが得策でしょう。


これが全体の概要図です。STLモデルビューア+Gコード生成するページを書いておいて、それで生成したGコードをSDカード経由でプリンタに移して使うというのが通常使用時の使い方になっています。プリンタ側はUIの提供とスレーブの管理をするボード、そして各軸について図のような配分のスレーブが三つで計四枚のボードからなります。

構造

アルミフレーム*4を使ってます。これはたまたま余ってたのですがかなり頑丈です。これのおかげで軸がgdgdでもなんとか動いていると言えるでしょう。

ヘッド・ステージ駆動

二相ステッピングモータのマイクロステップ駆動(もどき)です。PWMでなくΔΣ変調しているのでスイッチ*5が遅くてもなんとかなっています。機械的には横方向がリニアブッシュ+タイミングベルト、奥行き方向がスライドレール*6+タイミングベルト、高さ方向は長ネジだけで支持と移動の両方を兼ねています*7。こういう弱い設計はCNCフライス等では考えられないことですが、ほとんど荷重がないので問題ありません。

フィラメント押出



これが積層溶融方式の要となる、樹脂フィラメントの押し出し+加熱器です。およそ240℃(ABSの場合)に維持した金属ノズルにフィラメント(今回は直径1.75mm)を押しこむことで先から細いひも状になって出てきます。・・・と書くと簡単なのですが、これは結構力のいる工程で、充分な力を確保するのはなかなか面倒なことです。この写真の構造に落ち着くまでにヒータは三回、押出部分は六回ぐらい作りなおしてます。

制御

マスターはSTBee mini(CortexM3ボード)、スレーブは全てATmega88Pを使って上記の処理を行なっています。スレーブに関しては特に書くことはないですが、マスターについて。ARMはツールチェインを用意して、コンパイル+書き込みできるまでが大変と思われがちで、エラーをにらみつつ謎のMakefileと格闘したりすることもある(?)ような気がしますが、今回summon-arm-toolchainとSConsを使うと

import os

# common code
env=Environment(
    AS="arm-none-eabi-as",
    CC="arm-none-eabi-gcc",
    LINK="arm-none-eabi-ld",
    CCFLAGS="-mcpu=cortex-m3 -mthumb -std=gnu89 -Wall -O2",
    # --start-group automatically resolves circular dependency
    LINKFLAGS="-T stm32f10x_hd_flash_offset.ld --start-group", 
    CPPPATH=["#.","#vcom","#fat",
             "#./lib/STM32F10x_StdPeriph_Driver/inc",
             "#./lib/STM32_USB-FS-Device_Driver/inc",
             "#./lib/CMSIS/Core/CM3"],
    ENV={'PATH':"/home/xyx/sat/bin:"+os.environ['PATH']})

env.Append(BUILDERS=
    {"Bin":Builder(action="arm-none-eabi-objcopy $SOURCE -O binary $TARGET")
    ,"Symbol":Builder(action="arm-none-eabi-nm -n $SOURCE > $TARGET")
    ,"List":Builder(action="arm-none-eabi-objdump -h -D $SOURCE > $TARGET")
    })

# children
libpath=[
    'vcom','fat',
    'lib/STM32F10x_StdPeriph_Driver',
    'lib/STM32_USB-FS-Device_Driver',
    'lib/CMSIS/Core/CM3']
SConscript(map(lambda d:'%s/SConscript'%d,libpath),'env')

# targets
env.Program("fw.elf",
    Glob("*.c")+['lib/CMSIS/Core/CM3/startup.o'],
    LIBS=['cm3','stdperiph_drv','usb_drv','vcom','fat','c'],
    LIBPATH=libpath+['/home/xyx/sat/arm-none-eabi/lib/thumb'])
env.Bin("fw.bin","fw.elf")
env.Symbol("fw.symbol","fw.elf")
env.List("fw.list","fw.elf")

(トップレベルのSConstructのみ、数行のSConscriptがいくつか必要)
とかなり簡潔に書けたのでこれは結構お勧めです。ARM安いですし。

データ生成

データ生成について。STLをFileで読み込んでwebgl-experimentalと2dのcanvasに表示、Gコードは三角形を適当にスライス+ラスターにしたあともにょもにょっと生成して、data URLでダウンロードするというシンプルな(?)構成です。HTMLひとつとCoffeeScriptいくつかでfile://で動作します*8。

わざわざwebっぽい技術で固めたのは、適当なボードをプリンタ側につけてHTTPサーバとして動作させれば、完全にプラットフォーム非依存な形で(専用のUSBドライバやJavaを使うのに比べて)動かせるという目論見があったからですが、結局それはやってません。

はじめての数えきれないほどのいんさつ


左から順に、

  1. 手動での押し出し
  2. ハードコードした短いパス
  3. 〃した長いパス
  4. 任意のモデルへの対応 *9
  5. (それなりに)安定化

というプリンタの進化が見て取れます。最初はなにか出てるだけで楽しいものですがちょっと経つと「あ〜また失敗か」とぽいぽい捨てるようになるので、まぁそういうものですね。

あ、ちなみに冒頭の写真は印刷したての状態ではなく、

こういう状態のものをニッパで除去したものです。これは数分で出来ます。

今後

とりあえず動くようになった所で、これからどうしましょう、ということなのですが、とりあえずPrusa Mendelか何かをつくろうと思っています。というのも、今のこのプリンタはデータ化されてない設計も多く、部品の消耗に対応できないからです。

数年前ならいざ知らず、RepRapコミュニティがかなり大きくなった今の状況でずっと独自の設計、というのは作ってる時は楽しいのですが運用する上ではあまりメリットがありません。それでとりあえず小物をぱぱっと作れるような環境を作りたいな、と思っています。

さて、「ぱぱっと」というのはプリンタだけでできることではありません。3dモデルの作成というのは結構面倒な作業で、これをもっとてきとーな感じ、例えばなにか現物があってそれに合わせてハサミで紙を切り出すような、それと同じぐらい手軽にしたいものです。

これは環境からの3dモデル構築とか操作とか*10その辺の話題になってくるわけですが、その方面で「実際に自分が必要としているアプリケーション」を作り出すためにこのプリンタをフルスクラッチで作ったという側面もあります。既存のよくできた枠組みに完全に乗っかってしまうと、それがうまく動きすぎて外れることを恐れてしまうからです。

と格好いい感じでまとめてみましたが、まぁ気の向くままにぼちぼちやっていこうかと思います*11。

*1:2011/10/10 3dプリンタ作り始めました

*2:3dものづくり系SNS。特にRepRapコミュニティではよく使われている

*3:https://docs.google.com/leaf?id=0B6zCoyeuDn-pOTNkZGY3Y2ItMzRmZS00MzU4LWJhNGQtMGYzMWZhZGRkOGNj&hl=en_US 新しい変更はあまり反映されてないけれども

*4:ユキ技研 LECOFRAME 25シリーズ

*5:TA7291

*6:家具とかに使われてる安物。リニアガイドではない。

*7:M6なのでネジの撓みが無視できないが、今のところ問題は起きていない

*8:Chromeだと--allow-file-access-from-filesが必要でしたが

*9:かっこいい感じのhttp://www.thingiverse.com/thing:12108何かを印刷しようとしたものの玉砕

*10:kinect fusion覚えてますか

*11:generative artとかそういうのもおもしろそうです

3dプリンタ経過報告〜押出

さて、以前に3dプリンタつくる！と宣言してからひと月、最も懸念していたフィラメントを高温で押し出す部分が安定動作するようになりました。

構成は

  • PC
  • (仮想COM / USB)
  • STBee mini
  • (UART)*3
    • X軸制御
    • Y,Z軸制御
    • ヒータ・押し出し制御

という感じで、今はSTBee上のインタラクティブなシェルでコマンドを打って操作してます。最終的にはSDカードからデータを読み取って、スタンドアローンで動作させる予定です。

実際X軸はもう動くので、あとはY,Z軸制御基板を適当に作って、STLから制御用のデータを生成する何か(ここはWebGLで)を書くだけです。
…と順調に行くと良いのですが。

3dプリンタ作り始めました

さて、以前にSLS方式(レーザで粉末を固めるタイプ)で失敗したりもして、その後3dプリントからは離れていたのですが、近頃iModelaなどを見ていると、やっぱり手元に欲しいな〜という気持ちが強くなってきました。

そこで、今回はFDM方式(溶かしたプラスチックで線を描くタイプ)でとりあえず動くものを作ってみようということになりました。手持ちの部品*1を有効活用したいのと、bootstrapするところは自分で体験したいな〜ということで、RepRapの資産は使わずに自前でするつもりです。が、たぶん出来るものはHuxleyみたいなかんじになると思います。

また、今回のプロジェクトでは文書はGoogle Docsで管理することにしたので、それを最初から公開しつつやってみようと思います。

https://docs.google.com/leaf?id=0B6zCoyeuDn-pOTNkZGY3Y2ItMzRmZS00MzU4LWJhNGQtMGYzMWZhZGRkOGNj&hl=ja

*1:主に昔のプロジェクトの残骸

Minecraftにみる世界の「完全性」

さて、所謂箱庭ゲームで重要なのは

  1. 適度な自由度(世界へ局所的にしか干渉できないものの、その痕跡は残せること)
  2. 作ったものを眺める楽しみ

などだと思うのですが、これらを実現するひとつの方法として、何らかの(それほど複雑でない)規則でシミュレーションを行う、というのが挙げられるかと思います。

そこで今回はMinecraftを例にとって、計算と自己複製の観点からその世界の性質を見てみます。


(この記事はMinecraftそのものに対する批評ではありません！)

概要

Minecraftがどんなゲームなのかは実況を見るなり実際にプレイ(注:最新版は有料)するなりして頂くとして、ここからはある程度知っていることを前提に概要を示します。

まず特徴的なのは、この世界の要素は連続的か離散的かで大きく二分できるということです。そして、離散的な側は自明ではないもののセルオートマトン(以下CA)として扱えます。というのも、ブロックの状態は種類の他にいくつかの属性を持ち、植物の成長・流体の発展・レッドストーン上の信号伝搬・照明など考えてみても、その時間発展は離散的でなおかつある瞬間には狭い範囲にしか影響を与えないからです。*1

一方連続な側は各要素がそれぞれ(連続な)位置と速度を最低限持ちますが、共通性の高い規則は重力程度で、相互作用は疎です。

そしてこれらの性質の異なる世界を、要素間のメッセージパッシングによって結合しているとみなすことが出来るでしょう。*2

Minecraftが考察の対象としてもおもしろいのは、世界の大部分を占める離散的なブロックを比較的均一に扱えるからです。まず、レッドストーン回路についてみてみましょう。

レッドストーン回路と計算

レッドストーン(以下RS)回路は色々な要素を操作できますが、論理回路としての完全性を言うには、空気・RSトーチ・適当なブロック・RSワイアの四種類があれば事足ります。

とりあえず遅延を無視すると、RSワイアは0とOR、RSトーチが1とNOTの役割を果たすのでこれで組み合わせ回路としては完全です。実際にはRSトーチでは単位時間(0.1sec)の遅延が発生する上に、瞬時に信号が伝わるのは15セルまでなので完全性を証明するのは難しいですが、CPUを構成した例( http://www.youtube.com/watch?v=4PnPSlLWRig )などから、事実上なんでも作れると言えるでしょう。

また、遅延が至るところで発生するにも関わらず、最小時間幅というのが決まっているので、複雑な回路が同期式とも非同期式とも言えない、暗黙の局所的クロックを用いるような構成を取るのも興味深いことです。

さて、ここで注意しておかないといけないのは、TNTやピストンがあるとはいえ、RS回路自体を動的に作りだすことはできないので*3、あくまでも移動するのは信号のみであるということです。

プレーヤキャラクタの役割

唐突ですが、このモデルで、例えばプレーヤがブロックを置くという操作が、プレーやキャラクタ(以下PC)を媒介としてどのように行われるか見てみましょう。

  1. PC->CA: 座標と種別を指定して「置く」メッセージを発行
  2. CA->PC: 置けるかどうか判断して、状態変更+成功可否を返答
  3. PC: 所持アイテムの状態を変更

ちなみに、「インベントリで選ぶ」というような作業は図の黒線の下の部分、つまりプレーヤとPCのインターフェースに属することであって、画面表示などと同じく、Minecraft世界の「中」から見える情報ではありません。・・・もちろんゲーム性には大きく関わるのですが、ここでは世界について考えているのでモデルから除いたほうが話が簡単になる、ということです。

プレーヤは何でも作れる、もう少し厳密には、「有限時間である領域内のCAの状態を(ほぼ)任意に設定できる」ようになっています。これを支えるのがPCに可能な行動群なので、それを見てみましょう。

  1. 速度変化(制限あり)
  2. 全てのブロックのアイテム化もしくは破壊
  3. アイテムの拾得
  4. ブロックの設置
  5. 箱・炉・作業台の使用
  6. その他(攻撃など)
  7. PCの周囲の数万セルの曖昧な情報

2,3,5,6で全てのアイテムが有限時間で取得可能なことを保証し、
それと2,4を加えて任意の点に任意のブロックを設置可能なことを保証します。

また1について、PCには重力が作用するものの(ほとんどの)ブロックには重力が作用しないというのは極めて重要です。もし重力がないと移動は対称性の高い操作になり、ゲームというよりもカーソルがPCの形をしているマップエディタになってしまいますし、全てのブロックが重力に従うとただのheight mapになってしまって、世界の次元がひとつ落ちてしまいます。*4

7について、これは1-6と違い生身のプレーヤを介してのものです。プログラマブルなNPCがどのように行動を決めるのか？というのを考えてみると、7のような情報が必要になることが分かります。もちろん、ここではMinecraft世界では想像もつかないような非常に高度な情報処理が行われているわけです。

そして生命へ…？

さて、これらのことからPCが世界を書き換える速度には上限があるのです。巨大な構造物に張り巡らされたRS回路が見せる変化は時間的には制約されていないものの、空間的にはそれが存在する領域にとどまります。しかし、空間的にも非有界な変化を見せる構造を作りたい！と思ってしまうものです(少なくとも筆者はそうです)。これができれば、自動掘削だとか、成長する建造物だとか、移動する乗り物などが作れる(かもしれない)わけですね。

これには二つの方向性があるでしょう。それは、

  1. 世界のフラット化: 全体をひとつの規則で結合する
  2. 「充分に強力な」要素の導入

ですが、前者は莫大な計算リソースを必要とする上に生身のプレーヤが干渉する術がないので、実質的には2番目のみ可能ということになります。

比較的簡単なルール(いくつかのブロックの追加、など)で「充分に」を実現するのは大変面白い問題です。先ほどのPCの行動一覧で、1-6だけでも複雑なのですが、さらに7を劇的に簡素化して充分な状況判断が出来る必要があります。

3,5辺りに関してはBuildCraftが参考になります。6は既存のブロックでなんとかするとして、1,2,4,7をどうするかが問題になります。10分ほどで思いついたのが、次のような変更です。

  • BuildCraftを前提
  • ブロックを二種類追加
    • ひとつめは「ロボット」ブロック、自然数のパラメータn,mを持ち、RS信号でNPCに変化、nセル移動後(できなければ消滅)目の前のブロックをなんでも取る(とれなければ消滅)、その後mセル移動してブロックを一定の向きにおいて消滅、その他水・溶岩・敵に触れる、長距離の落下で消滅
    • ふたつめは「設定」ブロック、n,mはPCのみ操作できて、RS信号で隣の「ロボット」ブロックに設定を反映

さて、これは小さめの変更ですが、これで「完全性」が達成できるのでしょうか？暇ならば実際にMODを書いてみたいところですねー(書かないフラグ)

*1:ほとんどの部分は長時間変化せず、それ故に大規模な世界をほどほどのハードウェアで実現できるというのも重要な点です

*2:実際の実装がどうなっているかは知りません

*3:壊すことはできますが

*4:もし剛体物理に忠実なシミュレーションだと、何かの下を開ける、というような構造物を作るのに多くの種類の形状が必要となってしまいます。そのような例としてはSource/Garry's modなどが挙げられるでしょうか？

グラフ彩色とパス表現

無向グラフについて、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より少ない色数で追跡可能になるかどうかはよくわかりません。