【１】スー・モース数列（１）

スー・モース(Thue-Morse)数列は，非周期的自己相似数列である．

［１］０，１，２，３，４，５，６，７，・・・を２進数表記すると，

　　０，１，１０，１１，１００，１０１，１１０，１１１，・・・　　

［２］数字の総和を２で割った余りを計算すると

　　０，１，１，０，１，０，０，１，・・・

これはスー・モース数列と呼ばれるもので，この数列に自己相似という性質がある．たとえば，この数列をひとつ置きに選んでも同じ数列が得られる．最初の２つの数字を選ぶ，次の２つの数字を捨てるという操作を繰り返しても同じ数列が得られる．すなわち，この数列は非周期的ではあるが，まったくランダムではなく，強固な短期的・長期的構造をもっていて，同じ数字が３つ以上続くことはない．

ｎを２進展開したとき，現れる１の個数が奇数の場合ｔn＝１，現れる１の個数が偶数の場合ｔn＝０と定める．たとえば，ｎ＝２３では

　　２３＝（１０１１１）2→ｔ23＝０

　したがって，スー・モース数列｛ｔn｝は

　　０，１，１，０，１，０，０，１，

　　１，０，０，１，０，１，１，０，

　　１，０，０，１，０，１，１，０，

　　０，１，１，０，１，０，０，１，・・・

　ここには明確な回文構造が見られます．すなわち，先頭から２^n項があるとき，ビット単位に１と０を入れ替え，数列の後ろに連結します．すなわち， この数列に，部分列に各ビットの否定をとった部分列を付加すると

　　０

　　０１

　　０１１０

　　０１１０１００１

のように再帰的に構成できる．

［３］各世代は前の世代にその補数を加えればよい．たとえば，０１１０の補数は１００１であるから

０１１０＋１００１→０１１０１００１

［４］この数列を生成する別の方法もある．簡単な置換則

　　０→０１，１→１０

をもとに非周期的で再帰的に計算可能な数列を生成してみる．０から始めると

　　→０１

　　→０１１０

　　→０１１０１００１

　　→０１１０１００１１００１０１１０

　　→０１１０１００１１００１０１１０１００１０１１００１１０１００１

このような置換則はフラクタル幾何学でしばしば用いられますから，ご存知の方も多いと思います．リンデンマイヤー・システムと呼ばれる成長則です。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝