数学の世界には、単純なルールから予想外に複雑な挙動を示す整数列が存在します。その代表例が「ホフスタッター数列」です。これらは非線形漸化式（前の項の値によって、次に参照すべき項のインデックスが変化する数式）によって定義される数列の総称であり、その多くはダグラス・R・ホフスタッターの著書『ゲーデル、エッシャー、バッハ』を通じて世に知られました。
これらの数列の最大の特徴は、自分自身の過去の値を参照して次の値を決定する「自己参照的」な構造にあります。これにより、一見するとランダムに変動しているように見えながらも、深い数学的な秩序を秘めていることが分かっています。
Key Facts
- 定義の核： 非線形漸化式を用い、項の値が次の項を求めるためのインデックスとして機能する。
- 起源： 多くの数列が名著『ゲーデル、エッシャー、バッハ』の中で初めて提示された。
- メタフィボナッチ： Q数列に代表される、フィボナッチ数列をさらに一般化した「メタフィボナッチ数列」の先駆けである。
- 未解明な点： Q数列のように、すべての自然数において値が定義され続けるか（数列が「死なない」か）が証明されていないものがある。
基本となるホフスタッター数列
相補的な関係にあるFigure-Figure数列
Figure-Figure数列は、RとSという2つの数列が互いに補完し合うペアです。R数列は前の項の和で定義され、S数列は「R数列に含まれない正の整数」を昇順に並べたものとして定義されます。この相互依存的な関係により、2つの数列は密接に結びついています。
自己参照的なG数列とH数列
G数列およびH数列は、より直接的な自己参照構造を持ちます。G数列は $G(n) = n - G(G(n-1))$ という形式で定義され、H数列はさらに参照回数を増やした $H(n) = n - H(H(H(n-1)))$ という構造を持ちます。これらは単純な式でありながら、独特の数値パターンを生成します。
対になるFemale（女性）数列とMale（男性）数列
F（Female）数列とM（Male）数列は、互いの値を参照し合うことで定義されるペアです。Fの計算にMの値が必要であり、同時にMの計算にはFの値が必要という、相互再帰的な仕組みになっています。
メタフィボナッチの代表格：Q数列とその展開
ホフスタッター数列の中で最も有名なのがQ数列です。これは「メタフィボナッチ数列」と呼ばれる分野の最初期の例であり、フィボナッチ数列が「直前の2項を足す」のに対し、Q数列は「直前の項の値に基づいて、どの過去の項を足すかを決定する」という複雑なルールを持っています。
Q数列の挙動は非常にカオス的ですが、経験的な観察によれば、項を「世代」というブロックに分けることができることが分かっています。しかし、数学的な厳密な証明は乏しく、ある時点で参照先が1未満となり、数列が定義できなくなる（死ぬ）可能性さえ排除できていません。
Q数列の一般化：HuberとPinnのアプローチ
その後、Q数列はさらに拡張されました。ホフスタッターとグレッグ・フーバーは、参照するインデックスを調整した $Q_{r,s}(n)$ ファミリーを定義しました。この中で、V数列 $(r,s)=(1,4)$ は「死なない」ことが証明されていますが、W数列 $(r,s)=(2,4)$ は依然として謎に包まれています。
また、クラウス・ピンは定数 $i, j$ を導入してインデックスを左にシフトさせる $F_{i,j}(n)$ ファミリーを提案しました。これにより、元のQ数列では利用されなかった初期項が計算に組み込まれるようになります。
ホフスタッター・コンウェイ $10,000 数列
数学者ジョン・ホートン・コンウェイは、ある特定の再帰数列 $a(n) = a(a(n-1)) + a(n - a(n-1))$ の収束速度を解明した者に1万ドル（後に1千ドルに減額）の賞金を懸けました。この挑戦に対し、コリン・L・マローズが収束率を証明し、賞金を獲得しました。この数列の $a(n)/n$ は $1/2$ に収束することが知られています。
ホフスタッター数列のまとめ
| 数列名 | 定義の特徴 | 主な性質 |
|---|---|---|
| Figure-Figure (R, S) | Rは和、SはRに含まれない数の集合 | 相補的なペア構造 |
| G / H 数列 | 入れ子状の自己参照 | 単純な式から複雑なパターンを生成 |
| Female / Male (F, M) | 互いの数列を相互に参照 | 相互再帰的な依存関係 |
| Q 数列 | 項の値で参照先を決定 | カオス的挙動、メタフィボナッチの先駆け |
| $10,000 数列 | $a(a(n-1))$ を含む再帰 | $a(n)/n$ が $1/2$ に収束する |
Frequently Asked Questions
ホフスタッター数列とは何ですか？
非線形漸化式を用いて定義される整数列のグループです。最大の特徴は、数列の項の値自体が、次にどの項を参照して計算するかを決めるインデックスとして使われる「自己参照」的な性質にあります。
Q数列が「死ぬ」とはどういう意味ですか？
漸化式の計算過程で、参照すべきインデックス（例：$n - Q(n-1)$）が1未満になってしまうことを指します。数列の定義は通常1番目の項から始まるため、それより前の項を参照しようとすると計算が不可能になり、数列が停止してしまいます。
メタフィボナッチ数列とは何ですか？
フィボナッチ数列のように前の項を足し合わせる形式をとりながら、足し合わせる項の場所（インデックス）自体が数列の値によって動的に変化する、より高階な再帰数列のことです。
ホフスタッター・コンウェイ数列の賞金は何についてでしたか？
この数列の項 $a(n)$ を $n$ で割った値（$a(n)/n$）が $1/2$ に収束していく際の「収束速度」を数学的に特定することに対して賞金が懸けられていました。
これらの数列は実用的にどこで使われていますか？
主に純粋数学や計算理論、カオス理論の研究対象となっています。単純なルールから複雑な挙動が生まれるプロセスは、自然界の複雑系やコンピュータサイエンスにおける再帰処理の理解に寄与しています。
References
- , p. 73
- "Hofstadter Figure-Figure Sequence". .
- , p. 137
- "Hofstadter G-Sequence". .
- "Hofstadter H-Sequence". .
- "Hofstadter Male-Female Sequences". .
- "Hofstadter's Q-Sequence". .
- , pp. 1, 7
- , pp. 5–6
- , p. 3