数理解析研究所講究録
第 1849 巻 2013 年 50-5650

ペンローズタイリング上でとぶ
グライダー
塚本靖之

宮崎雄平

立木秀樹

京都大学

人間・環境学研究科

Graduate School of Human and Environmental Studies,
Kyoto University
概要

ペンローズタイリング上の状態数 3 の半総和的セルオートマトンで，グライダーが存在するものを構成した．これを元に，状態数4 のセルオートマトンで計算万能性を持つものも構成できる．この例は，準周期的なタイリング上のセルオートマトンで計算万能性が示されているものの中では最も状態数が少ない．

1

タイリング上の有限個の点の凸包で，内点を持つものを凸多角形という．タイリングを構成する多角形は，凸多角形であるか，有限個の凸多角形の和集合 で，とその内部 int $(c)$ がともに可縮なものとする．
$\mathbb{R}^{2}$$c$

定義 1.1.

$c$$\mathbb{R}^{2}$のタイリング $T$ とは，可算個の多角形の集合$\bigcup_{i\in I}c_{i}=\mathbb{R}^{2}$$\forall i,j\in I,$$\{c_{\dot{2}}\}_{i\in I}$であって，(1),$i\neq j\Rightarrow$int$(c_{i})\cap$

int$(c_{j})=\emptyset$(2)を満たすものとする．

タイリングの元をセルと呼ぶ．セル $c\in T$ に対し，の近傍を$c$$N(c);=\{c_{j}\in T|c\cap c_{j}\neq\emptyset\}\backslash \{c\}\subset T$で定める．この近傍はムーア近傍と呼ばれるものである．

(3)

51

2

半総和的セルオートマトン
タイリング $T$ とその近傍の取り方 $N$ , 自然数$\mathbb{N}$$\mathbb{N}$は非負整数の集合とする．自然数$n\in \mathbb{N}$$s\in \mathbb{N}$を固定する．ただし，に対し，$[n]:=\{0,1, \ldots, n-1\}\subset$とおく．

タイリングから $[s]$ への写像を配置 (configuration) と呼ぶ．配置 q. に$T$

$q(c)(c\in T)$ をおいて，$c$の状態 (state)という．状態$0$のセルを死亡セル，それ以外のセルを生存セルと呼ぶ．
セル $c\in T$ と配置 に対し，
$q$$n(c, q);=(n_{0}, \ldots, n_{s-1})\in \mathbb{N}^{s},$(4)$\forall k\in[s], n_{k}=\#\{c_{j}\in N(c)|q(c_{j})=k\}$

とおく．写像 :$f$$[s|\cross \mathbb{N}^{s}arrow[\mathcal{S}]$を固定し，(5)$\forall c\in T, \delta(q)(c)=f(q(c), n_{0}, \ldots, n_{s-1})$

によって，配置から次の配置を与える遷移関数 を定める．式 (5)のように表される規則 $f$ を半総和則 (semi-totalistic rule) という．
$q$$\delta(q)$$\delta$$T$
定義 2.1. 4 つ組 $(T, N, s, f)$ を，上で近傍の取り方 $N$ , 状態数 , 局所
規則 $f$ の半総和的セルオートマトン (semi-totalistic cellular automaton)$\grave{}$$\mathcal{S}$という．

以降，セルオートマトンの局所規則は半総和則とする．また，局所規則において，近傍の死亡セルの個数 は無視する．
$n_{0}$

例 2.2. 正方格子のタイリング $T$ , ムーア近傍 $N$ , 状態数 2, 局所規則
$f(i, n_{0}, n_{1})=\{\begin{array}{l}1 ((i, n_{1})=(0,3), (1,2)_{1}(1,3))0 (それ以外)\end{array}$(6)のセルオートマトン $(T, N, 2, f)$ をコンウェイのライフゲームという．

コンウエイのライフゲームは計算万能性を持つことが知られている．

3

ペンローズタイリング

ペンローズタイリングのうち，2 種類の菱形にょる平面のタイリングを扱う (図 1) 構成法は省略するが，重要な性質をあげる．

52
ペンローズタイリング $P=\{d_{i}\}_{i\in I}$ は周期的ではない．つまり，$P,$ $d_{i}+v:=\{x+v|x\in d_{i}\}\in P$ となるようなは存在し$\forall d_{i}\in$$v\in \mathbb{R}^{2}\backslash \{(0,0)\}$ない．

しかし，任意の有限集合$J\subset I$に対し，ある$v\in \mathbb{R}^{2}\backslash \{(0,0)\}$

が存在

して，

(7)

$\forall j\in J, d_{j}+v\in P$となる．この性質を準周期的であるという．
$P$ではさらに，$\bigcup_{j\in J}d_{j}\subset b\mathbb{R}^{2}$の幅と高さの上界に対し，ある定数 が$l$存在して， の一辺の長さが の任意の正方形の領域に，式 (7) を満たす$\mathbb{R}^{2}$

$v$

$l$

が存在する．

4

グライダー
セルオートマトン $(T, N, s, f)$ においてグライダーと呼ばれる，移動し続ける集団が発生することがある．
定義 4.1. グライダーとは，配置であって，次の条件を満たすものとす
とおく．
る．配置 に対し，Alive$g$$(q):=T\backslash q^{-1}(0)$$q$1. $0<\# Alive(g)<\infty.$

2.

$n\neq m\Rightarrow\delta^{n}(g)\neq\delta^{m}(g)$3.

$\forall m\in\backslash \mathbb{N},$$\exists n>m,$.

$\exists v\in \mathbb{R}^{2}$, st.

$\forall k\in[s]\backslash \{O\},$$(\delta^{n}(g))^{-1}\backslash (k)=\{c+$$v|c\in g^{-1}(k)\}.$

ただし$\delta$は $f$ から定まる遷移関数である．

条件 3 は，生きているセルに制限した場合に平行移動した配置が無限に現れるという意味であるが，別の定義もあり得るところである．
定理 4.2 (A. Goucher). ペンローズタイリング $P$ 上のセルオートマトン$(P, N,4, f)$ で，グライダーが存在するような局所規則 $f$ が存在する．

四角形から成るタイリング $T$ のセルの列て$r_{n},$$r_{n+1}$が互いの辺で接しており，$(r_{n})_{n\in \mathbb{N}}$$r_{n}\cap r_{n+1}$

で，各$n\in \mathbb{N}$についと $r_{n+1}\cap r_{n+1}$ が $r_{n+1}$ の向かい合う辺となっているようなものをリボンという．

Goucher のグライダーはリボンに沿って移動しつづける．ペンローズ$m\neq n$ ならば $r_{m}\neq r_{n}$ であり，タイリング $P$ の任意のリボンについて，$\{r_{n}|n\in \mathbb{N}\}^{1}\subset P$が準周期的であることが知られている．

53
表 1: グライダーがとぶ局所規則の例．アスタリスク$*,$,の欄は任意である．より上にある規則を優先する．

注意 4.3. ペンローズタイリング上で局所規則 (6) をそのまま適用したセルオートマトンにおいては，グライダーは発見されていない．

Goucher のグライダーを元に，状態数がより小さいグライダーを構成した．

定理 4.4. ペンローズタイリング $P$ 上のセルオートマトン $(P, N, 3, f)$ で，グライダーが存在するような局所規則セルのを$c$$c$に対し， int$c\backslash$$(c)$$f$が存在する．に含まれる線分で，包含関係につぃて極大なもの辺と呼ぶ．また辺の端点を頂点と呼ぶ．グライダーが飛ぶ条件は次のようになる．

1. セルは全て四角形である．
2. 任意の異なる 2 個のセル

$c,$$c’\in T$について，c$\cap C$’ は空であるか，双方の辺または頂点となる．

3. どの 2 個も接しているような 3 個の $*$ )$c”\neq\emptyset$$\triangleright c,$$c’,$ $c”\in

T$ について $c\cap c’\cap$となる．

4. 隣り合う 2 個の頂点について，どちらかの次数は 4 以上である．
ただし，Goucher のグライダーでは条件 4 は不要である．

Proof. 局所規則を表 1 のようにする． 上のリボン$P$る．配置$g$を$g(c)=\{\begin{array}{l}1 (c\in\{r_{1}, r_{2}\})2 (c=r_{0})0 (それ以外)\end{array}$$(r_{n})_{n\in \mathbb{N}}$をーつ固定す54

図 1: $P$ 上のグライダーの例

で定める (図 1).

$g$がセルオートマトン $(P, N,3, f)$ におけるグライダーとなる．

局所規則から，$\delta(g)(c)=\{\begin{array}{l}1 (c=r_{2})2 (c\in N(r_{1})\cap N(r_{2}))0(それ以外)\end{array}$において，状態 1 のセルが のみだから，Aliveとなる．配置$\delta(g)$$\{r_{2}\}\cup N(r_{2})$である．

$r_{2}$$(\delta^{2}(g))\subset$$\#(N(r_{1})\cap N(r_{2}))\geq 3$ より，次数 3 の頂点が隣り合わないことから，$\#(N(r_{1})\cap N(r_{2})\cap N(r_{3}))=2$を得る．となる．状態 2 のセルは次の配置で状態 だから，である．上記以外のセル $c\in N(r_{2})$ にが示される．
こおいて $n_{2}=1$ より，$\delta^{2}(g)(r_{1})=2,$ $\delta^{2}(g)(r_{2})=1$

から，

$0$

$\delta^{2}(g)(r_{3})=1$$\delta^{2}(g)(c)=0(\forall c\in N(r_{1})\cup N(r_{2}))$

ついては配置$\delta(g)\ovalbox{\tt\small REJECT}$$\delta^{2}(g)(c)=0$

以下，これを繰り返して帰納的に$\forall n\in N,$を得る．集合$\delta^{2n}(g)(c)=\{\begin{array}{l}1 (c\in\{r_{n+1}, r_{n+2}\})2 (c=r_{n})O (それ以外)\end{array}$$\{r_{n}|n\in \mathbb{N}\}$の準周期性より， はグライダーである．口$g$

55

5

計算万能性

コンウェイのライフゲームでは，適当な初期状態 (初期配置) と受理．
非受理の状態を与えることで，チューリングマシンを模倣できることが知られている．この証明で，グライダーを発射し続けるグライダー銃の配置が計算の主要な部分を担う．グライダーを構成したのは，ペンロー
ズタイリング上のセルオートマトンで同じことをするためでもある．
2 個の配置 $p,q$ に対し，Alive $(p)\cap$ Alive ($q)=\emptyset$であるとき，和 $p+q$ を$\forall c\in T, (p+q)(c):=p(c)+q(c)$で定める．

定義 5.1. グライダー銃 $G$ とは，配置であって，$\exists g$:glider,$\exists m\in \mathbb{N},$$s.t. \delta^{m}(G)=G+g, \forall n\in \mathbb{N},, \delta^{n}(G+g)=\delta^{n}(G)+\delta^{n}(g)$を満たすものとする．

状態数を 4 とし，前節で紹介したグライダーを発射し続けるグライダー銃を構成した．
定理 5.2. ペンローズタイリング $P$ 上のセルオートマトン $(P, N, 4, f)$ で，グライダー銃が存在するような局所規則$f$が存在する．

状態数 4 のまま，規則をうまく定めれば，グライダー銃のみならず，レセプターとスイッチが構成できる．それらを配置すると，AND ゲート，NOT ゲートを構成でき，さらに配線も自由に行えるようにできる．ゲートが働くためには信号の同期が必要であるが，それは各ゲートで用いるグライダー銃の位相を合わせるだけでよい．
定理 5.3. セルオートマトン $(P, N, 4, f)$ が計算万能性を持つような局所規則 $f$ が存在する．

定理 5.2,5.3 の証明は省略する．

謝辞．ペンローズタイリング上のセルオートマトンを研究するきっかけをくださった今井克暢先生に感謝いたします．また，本研究の一部は科研費 (22500014) の助成を受けています．

56

参考文献
[BCG] Berlekamp, E., Conway, J., Guy, R., Winning Ways for Your, second edition, A K Peters, Ltd. (2001).
Mathematical$Play\mathcal{S}$[G]

Goucher, A., Gliders in cellular automata on Penrose tilings,
http: $//cp4$ space.files. wordpress. com/2012/11/2012-penrose

gliders. pdf[IHPS] Imai, K., Hatsuda, T., Poupet, V., Sato, K., A Universal Semitotalistic Cellular Automata on Kite and Dart Penrose Tilings, E.
Formenti (Ed.): AUTOMATA and JAC 2012 conferences EPTCS
90, 2012, pp. 267–278.
[S]

Schiff, J., Cellular Automata; Discrete View of the World, John
Wiley & Sons, Inc. (2008).
梅尾博司，Ferdinand Peper 監訳『セルオートマトン』共立出版，$A$$2011$.