roombaの日記

読書・非線形科学・プログラミング・アート・etc...

ハンバーガーとしてのカントール集合と、L-systemによる表現

この記事では、ハンバーガーとの対比により、カントール集合というフラクタルの一種を理解することを目指します。パンの塊に対して「ある簡単な操作」を無限回繰り返してゆくと、無限枚のパンが含まれるにもかかわらずパンの割合が0%という奇妙なハンバーガーが出来上がるのです。
さらに、この奇妙なハンバーガーをL-systemという一種の形式言語によって記述したり、問題をビッグマックに拡張したりもします。

目次

パンをハンバーガ―にする変換

下図のようなパンの塊があったとしましょう。このパンからハンバーガーをつくるにはどうしたら良いでしょうか?
f:id:roomba:20151001230321p:plain

いろいろと方法はあるでしょうが、ここでは次のように考えてみます。

「パンの中央三分の一をくりぬき、代わりにハンバーグで埋める」

横から見ると以下のようなイメージです。肌色がパン、茶色がハンバーグに対応します。
f:id:roomba:20151001230550p:plain
この記事では、これを「ハンバーガー変換」と呼ぶことにしましょう。

「ハンバーガー変換」:
パンの中央3分の1をくり抜き、代わりにハンバーグで埋める変換

無限回のハンバーガー変換

ハンバーガー変換をハンバーガーに行う

前章では、パンの塊をハンバーガーにする「ハンバーガー変換」なるものを定義しました。では、ハンバーガーに対して「ハンバーガー変換」を行うとどうなるでしょうか?

ハンバーガーにはパンの部分が上下に二か所存在しており、それぞれのパンに対して「ハンバーガー変換」を実行することになります。この操作によって、ハンバーガーによってハンバーグを挟んだ新たなハンバーガーが出来上がりますね。下図を見れば一目瞭然でしょう。
f:id:roomba:20151001231037p:plain

ハンバーガー変換を無限回行う

パンの塊にハンバーガー変換を行うとハンバーガーになり、ハンバーガーにハンバーガー変換を行うと「ハンバーガーによってハンバーグを挟んだもの」になり、……というふうに、ハンバーガー変換を永遠に繰り返すとどうなるかを考えてみましょう。図をみてください。
f:id:roomba:20151006171640p:plain
ハンバーグの割合が増えてゆき、限りなく100%に近づきそうな気がしますね。

すべてがハンバーグになる

f:id:roomba:20151001230550p:plain
「ハンバーガー変換」の定義に立ち返って考えれば、1回のハンバーガー変換によって

  • パンの割合は2/3倍 (残りの1/3がハンバーグに置換される)
  • パンの枚数は2倍 (それぞれのパンがハンバーグにより2つに分断される)

となることが分かります。

したがって、変換をn回行ったあとのパンの割合は
{\displaystyle
(\frac{2}{3})^n
}
となり、変換をn回行ったあとのパンの枚数は
{\displaystyle
2^n
}
となります。
無限回のハンバーガー変換を考えると、パンの割合は
{\displaystyle
\lim_{n \to \infty}(\frac{2}{3})^n = 0
}
パンの枚数は
{\displaystyle
\lim_{n \to \infty} 2^n = \infty
}

したがって、無限回のハンバーガー変換を繰り返すことにより、
無限枚のパンが含まれるにもかかわらずパンの割合が0%
という奇妙なハンバーガーができることが確認されました。
ただし、パンの割合が限りなく0%に近づくということであって、決して完全な0%になることはありません。

カントール集合

実を言うと、無限回のハンバーガー変換によって構成された奇妙なハンバーガーは、カントール集合と同等であるということができます。
カントール集合とは、Wikipediaによれば以下のような集合です。

カントール集合は、幾何学的には、線分を3等分し、得られた3つの線分の真ん中のものを取り除くという操作を、再帰的に繰り返すことで作られる集合である。

カントール集合 - Wikipedia

f:id:roomba:20151006172403p:plain
「線分を3等分し、得られた3つの線分の真ん中のものを取り除くという操作」を「パンを3等分し、得られた3つのパンの真ん中のものをハンバーグに置き換えるという操作」と読み替えればいいというわけです。

ちなみに、カントール集合および「奇妙なハンバーガー」は自己相似(フラクタル)になっています。すなわち、「奇妙なハンバーガー」の上側(or下側)3分の1は「奇妙なハンバーガー」自身と相似になっています。

L-system

カントール集合は、L-systemというアルゴリズムによって再帰的に記述されることが一般に知られています。そこで、本記事でつくった「奇妙なハンバーガー」もL-systemによって記述してみましょう。

L-systemとは

Wikipediaを見ると以下のような説明がなされていますが、理解できなくても結構です。

ざっくり言うと、文字を別の文字に置き換える「置換ルール」と「初期の文字列」の組みあわせを決めておき、「初期の文字列」をスタートとして「置換ルール」を何度も(再帰的に)適用することで複雑な文字列を得ることができるという感じでしょうか。そうして得られた複雑な文字列を図形に対応付けることで様々なフラクタル図形等を描くこともできます。

上記の「置換ルール」が以下の引用におけるPに相当し、「初期の文字列」が以下のωに相当します。

L-system は下記のようなタプルとして定義される「パラメトリック L-system」として一般に知られている。
G = {V, S, ω, P},
上記において、各要素は以下の意味を持つ。

  • V(文字): 置換規則(後述の P )により順次置き換えられてゆく変数の集合。L-system の再帰的な反復計算が進んでいく時に、物として「成長」してゆくのはこの V の要素からなる文字列である。
  • S : 計算が進んでも変化しない定数の集合。
  • ω : システムの初期状態を示すV の要素からなる文字列。
  • P : V を変化させてゆく置換規則の集合。各要素は、例えば (A → AB) のように、置換前(置換対象)の文字列と置換後の文字列の組み合わせにより記述される。

L-system - Wikipedia

L-systemによる「奇妙なハンバーガー」の記述

L-systemによってカントール集合を記述する方法として、Wikipediaでは以下のように説明されています(一部改変)。

  • V : A, B
  • S : なし
  • ω: A
  • P : (A → ABA), (B → BBB)

計算を進めると、以下のような文字列となる。
n = 0 : A
n = 1 : ABA
n = 2 : ABABBBABA
n = 3 : ABABBBABABBBBBBBBBABABBBABA
この文字列の A を線分、B を抜き取られた部分に置き換えるとカントール集合が得られる。置換規則の (A → ABA) は線分(閉区間)を3等分して中央を抜き取る操作に相当する。(B → BBB) は一度取り除かれた区間が戻らない事を意味する。

L-system - Wikipedia

ハンバーガー変換を繰り返して得られる「奇妙なハンバーガー」も全く同じように記述することができます。
文字Aをパン、Bをハンバーグとみなせば置換規則の (A → ABA) はハンバーガー変換に相当します。(B → BBB)はスケールの調節のようなものです。

拡張:ビッグマック変換

ビッグマック変換の定義

ここまではパンをハンバーガーにする変換を考えましたが、パンをビッグマック(パン、肉、パン、肉、パンと並ぶ)にする変換を考えてみましょう。

ビッグマック変換」:
パンを1/5に切断し、上から2番目・4番目をハンバーグに置き換える変換
f:id:roomba:20151006175806p:plain

無限回のビッグマック変換

ハンバーガー変換のときと同様に考えれば、1回のビッグマック変換によって

  • パンの割合は3/5倍
  • パンの枚数は3倍

となります。

パンの塊にビッグマック変換を無限回繰り返すと、パンの割合は
{\displaystyle
\lim_{n \to \infty}(\frac{3}{5})^n = 0
}
パンの枚数は
{\displaystyle
\lim_{n \to \infty} 3^n = \infty
}
この場合も「無限枚のパンが含まれるにもかかわらずパンの割合が0%」となりますね。

L-systemによる記述

文字Aをパン、Bをハンバーグとみなせば、ビッグマック変換は置換規則 (A → ABABA) として表現できます。(B → BBBBB)はスケールの調節のようなものです。

  • V : A, B
  • S : なし
  • ω: A(パンの塊を初期状態とする)
  • P : (A → ABABA), (B → BBBBB)

計算を進めると、以下のような文字列となる。
n = 0 : A
n = 1 : ABABA
n = 2 : ABABABBBBBABABABBBBBABABA

ハンバーガーのときとほとんど同じですね。

おわりに

パンとハンバーグが何層も串刺しにされている、食べにくそうなハンバーガーをみたときに思いつきました。ハンバーガーに例える必要は無かったような気もしてきましたが、それは考えないことにします。