エラトステネスの篩って「採譜」できるだろうか？
筆者は数学側の人間で、音楽については素人です。記譜の慣習(D.C. や反復記号の扱いなど)や作品の紹介に、誤りがあるかもしれません。見つけたらコメントで教えてください。
はじめに:篩を楽譜に書きたい
エラトステネスの篩を、楽譜に書けるでしょうか。
具体的には、1拍目、2拍目、3拍目、…と数えていき、素数の拍でだけ音を鳴らし、それ以外は休符にする楽譜を考えます。2, 3, 5, 7, 11, 13, … 拍目にだけ音が鳴る、いわば「素数のリズム」です。
100拍目まででよければ簡単です。素数を調べて、該当する拍に音符を書けば終わりです。でもそれは、篩を計算した結果を写しているだけです。欲しいのは、篩の手順そのものを楽譜の記号で書き表して、演奏すれば素数のリズムが永遠に鳴り続ける楽譜です。
望みはありそうに見えます。楽譜を眺めていると、
- 反復記号(リピート)は ループ っぽい
- 1番括弧・2番括弧は if 文 っぽい
- D.C. や D.S. は goto っぽい
ことに気づきます。ループと分岐と goto があるなら、楽譜でプログラムが書けてしまうのでは？ もっと言えば、五線譜の記法はチューリング完全なのでは？
先に結論を言ってしまうと、無理です。素数のリズムを鳴らし続ける楽譜は、D.C. で無限ループを許しても書けません(第4節で証明します)。理由をひとことで言うと、
楽譜は数を覚えられないから
です。反復の回数は楽譜に書かれた定数で、演奏しながら増えたり減ったりする変数がどこにもありません。この記事では、このひとことの意味を、具体例 → ゆるい説明 → 厳密な証明の順に見ていきます。
厳密な証明に興味がない人は、3.2節を飛ばして読んでも話の筋はつかめます。
1. 楽譜を「実行」してみる
まずは、楽譜を読むことがどれだけプログラムの実行に似ているか、例で確かめましょう。A〜E の5小節からなる、次のような楽譜を考えます。
| A |: B | C :| D (Fine) | E (D.C. al Fine) |
これを演奏すると、こうなります。
- A を弾く
- 反復区間 B C を2回弾く → B C B C
- D を弾く(Fine はまだ無視)
- E を弾き、D.C. で先頭に戻る
- A を弾く
- B C を弾く(D.C. の後は反復を省略するのが慣習)
- D で Fine。終わり
実際に鳴る小節の列は
$$ A\ B\ C\ B\ C\ D\ E\ A\ B\ C\ D $$
です。楽譜という「ソースコード」を、演奏者という「処理系」が実行して、小節の列という「出力」を得ている。こう見ると、たしかにプログラムっぽいですね。
ここで、演奏者が弾きながら覚えておく必要があることを書き出してみます。
- いまどこを弾いているか(位置)
- 各反復区間を何回弾いたか(反復カウンタ)
- D.C. などのジャンプをもう使ったか(フラグ)
これだけです。実は、この「覚えておくことリスト」が短くて有限だという点に、答えのすべてが詰まっています。
2. チューリング完全ってなんだっけ
ざっくり言うと、ある言語がチューリング完全であるとは「どんな計算でもその言語で書ける」ことです。Python や C はもちろん、Excel の数式も(LAMBDA 関数が入ってからは)チューリング完全です。
チューリング完全になるために必要なものは、実はかなり少なくて済みます。
次の命令だけを持つ機械は、チューリング完全である。
- 自然数を値に持つ、上限のないカウンタが2つ
- カウンタを 1 増やす / 1 減らす命令
- 「カウンタが 0 かどうか」で分岐する命令
ポイントは、上限のない記憶と、その値を見て分岐する仕組みの2つです。どちらかが欠けると、チューリング完全には届きません。
では、楽譜はどうでしょうか。
3. 楽譜に足りないもの
3.1 ゆるい説明
第1節の「覚えておくことリスト」を、もう一度見てみます。
- 位置:楽譜の長さを超えることはない
- 反復カウンタ:楽譜に書かれた回数(ふつうは2回)を超えることはない
- ジャンプのフラグ:使ったか、使っていないかの2通り
どれも、楽譜を見た時点で上限が決まっています。演奏中に「さっきの値に1を足して覚えておく」ような、上限のない記憶はどこにもありません。
ここで、導入で「if 文っぽい」と書いたボルタ(1番括弧・2番括弧)を思い出してください。ボルタは「いま何周目か」という反復カウンタを読んで、弾く小節を切り替えます。第2節の言葉で言えば、これはカウンタの値を見て分岐する仕組みそのものです。つまり楽譜は、チューリング完全に必要な2つの材料のうち、分岐のほうはすでに持っています。
足りないのは記憶のほうです。ボルタが読むカウンタには、次の制限があります。
- 楽譜に書かれた反復回数という上限がある
- 周回ごとに1増えるだけで、減らせない
- その反復区間の中でしか使えず、外から読んだり操作したりできない
上限のあるカウンタは取りうる値が有限です。そのため、分岐があっても全体は有限状態のままです。
記憶のパターンが有限なら、演奏者の状態も有限通りしかありません。有限通りの状態しか取れない機械は有限オートマトンと呼ばれ、チューリング機械よりずっと弱い計算モデルです。
さらに、標準的な慣習(D.C. は1回だけ、反復は書かれた回数だけ)を守る限り、後ろに戻るジャンプの回数はすべて決まっています。そのため、どんな楽譜の演奏も必ず終わります。チューリング完全な言語なら「止まらないプログラム」も書けるはずなので、この時点でチューリング完全ではありえません。
3.2 厳密版(読み飛ばしOK)
ここからは、上の話をきちんと証明します。
楽譜を有限列 $S = s_0 s_1 \cdots s_{n-1}$ とみなします。各 $s_i$ は、音の出来事(音符・休符など)か、制御記号です。制御記号には、反復開始 $\mathsf{RS}$、反復終了 $\mathsf{RE}_m$(区間を計 $m$ 回演奏)、ボルタ、$\mathsf{DC}$, $\mathsf{DS}$, $\mathsf{Fine}$, $\mathsf{ToCoda}$ などがあります。反復は入れ子にせず、$\mathsf{DC}, \mathsf{DS}, \mathsf{ToCoda}$ はそれぞれ1個まで、とします。
楽譜 $S$ の状態とは、組 $\gamma = (p, c, g)$ のことである。
- $p \in \{0, \dots, n\}$:現在位置
- $c(r) \in \{1, \dots, m_r\}$:各反復区間 $r$ をこれまでに弾いた回数
- $g \subseteq \{\mathsf{DC}, \mathsf{DS}, \mathsf{ToCoda}\}$:使用済みのジャンプ
第1節の演奏規則から、次の状態を返す部分関数 $\delta$ が決まる。$\delta$ が未定義になったら演奏終了とする。初期状態 $(0, \mathbf{1}, \varnothing)$ から $\delta$ を繰り返して得られる音の列を、演奏 $[\![S]\!]$ と呼ぶ。
ボルタは、この定義の中では「現在の周回数 $c(r)$ が括弧に書かれた番号でなければ、括弧の終わりまで読み飛ばす」という規則として入っています。つまり、楽譜が分岐の判断に使える値は $c(r)$ だけです。そして $c(r) \le m_r$ なので、その値は有限通りしかありません。これが3.1節の「分岐はあるが、記憶に上限がある」の厳密版で、次の命題の中身です。
状態全体の集合 $\Gamma$ について、次が成り立つ。
$$
|\Gamma| \le (n+1) \cdot \prod_r m_r \cdot 2^3
$$
任意の楽譜 $S$ について、演奏は有限ステップで終わる。
状態 $\gamma = (p, c, g)$ に対して
$$
\rho(\gamma) = \Bigl(\, 3 - |g|,\ \textstyle\sum_r (m_r - c(r)),\ n - p \,\Bigr) \in \mathbb{N}^3
$$
とおき、$\mathbb{N}^3$ に辞書式順序を入れる。この順序は整礎なので、各遷移で $\rho$ が真に減ることを確かめればよい。
- 前に進む:$p$ が増えるので、第3成分が減る。
- 反復で戻る:ある $c(r)$ が 1 増えるので、第2成分が減る。
- D.C. などで飛ぶ:$|g|$ が 1 増えるので、第1成分が減る。
整礎な順序で真に減り続ける列は有限なので、演奏は終わる。
$\square$
証明を追うと、演奏の長さは、楽譜の長さ $n$ と最大の反復回数 $M$ を使って $4nM$ 以下だとわかります。
これを使って主定理を示します。チューリング完全性の定義にはいろいろな流儀がありますが、ここではかなり条件をゆるくした、次の定義を使います。
記法 $L$ が弱チューリング完全であるとは、次の2つが存在することをいう。
- チューリング機械 $\mathcal{M}$ を楽譜 $T(\mathcal{M})$ に変換する、計算可能な写像 $T$
- 演奏に関する、決定可能な性質 $\varphi$
ただし、これらは次を満たすとする。
$$
\mathcal{M} \text{ が停止する} \iff [\![T(\mathcal{M})]\!] \text{ が終わり、かつ } \varphi([\![T(\mathcal{M})]\!])
$$
「停止したら合図の音を鳴らす」のような、どんなに緩い符号化でもよい、という定義です。ゆるい定義でダメなら、もっと厳しい定義でもダメです。
五線譜の記法は、弱チューリング完全ではない。
そのような $T, \varphi$ があったとする。チューリング機械 $\mathcal{M}$ が与えられたら、次の手順を実行する。
- 楽譜 $S = T(\mathcal{M})$ を計算する。
- 演奏を高々 $4nM$ ステップ実行し、$[\![S]\!]$ を得る。前の定理より、これは必ず終わる。
- $\varphi([\![S]\!])$ を判定する。
この手順は必ず止まり、$\mathcal{M}$ が停止するかどうかを正しく答える。これは停止問題の決定不能性に矛盾する。
$\square$
4. でも、D.C. を使えば無限ループできるのでは？
ここで、鋭い人はこう思うはずです。
D.C. を「到達するたびに有効」と読めば、永遠に終わらない楽譜が作れるのでは？
そのとおりです。たとえば $A\ B\ \mathsf{DC}$ という楽譜をこのルールで演奏すると、$ABABAB\cdots$ と永遠に続きます。実際、終わりを持たずに冒頭へ戻り続ける無限カノン(canon perpetuus)という形式もあります。
ただ、これでもチューリング完全にはなりません。状態が有限通りであることは変わらないからです。
状態は高々 $N = |\Gamma|$ 通りしかない。$N$ ステップ以内に演奏が終わらなければ、ある状態が二度現れたことになる。演奏は決定的なので、そこから先は同じ周期を永遠に繰り返す。
よって「演奏が終わるか」は $N$ ステップ弾いてみれば判定でき、主定理の証明はそのまま通る。
つまり、第3節で見た「必ず終わる」は、実は本質ではありませんでした。本当に効いているのは、「状態が有限通りしかない」ほうです。
4.1 素数のリズムは鳴らせない
この注意の証明をもう少し読むと、もっと強いことがわかります。状態が二度現れたら、そこから先の演奏は同じ周期の繰り返しです。つまり、無限ループする楽譜の演奏は、必ず
$$
u\ v\ v\ v\ \cdots
$$
(最初に有限の列 $u$、その後は同じ列 $v$ の繰り返し)という形になります。このような列を最終周期的な列と呼びます。
ここで、冒頭の問いに戻りましょう。
$n$ 拍目が素数なら音、そうでなければ休符とする無限列は、最終周期的ではない。したがって、D.C. による無限ループを許しても、この列を演奏する楽譜(演奏者に選択を委ねない楽譜)は存在しない。
最終周期的だと仮定すると、ある $N$ と周期 $p \ge 1$ があって、$n \ge N$ なら「$n$ が素数」と「$n + p$ が素数」が同値になる。素数は無限にあるので、$N$ 以上の素数 $q$ がとれる。周期性を $q$ 回使うと、$q + qp = q(1+p)$ も素数でなければならない。しかし $1 + p \ge 2$ なので、$q(1+p)$ は合成数である。これは矛盾である。
$\square$
5.2節のように、演奏者に選択を委ねる記号を許すと話は変わる。たとえば「毎拍、音を鳴らすか休むかを演奏者が選ぶ」という楽譜は、素数のリズムどおりに選んだ演奏も許す。しかしこの楽譜は、素数のリズム以外のあらゆるリズムも同じように許してしまう。素数のリズムを選び出しているのは演奏者の頭の中の篩であって、楽譜ではない。定理が「演奏者に選択を委ねない」と断っているのはこのためである。
篩は「これまでに見つけた素数の倍数を消していく」手順です。見つけた素数のリストは際限なく伸びていくので、篩を回すには上限のない記憶が必要です。楽譜には、それを置く場所がありません。
4.2 螺旋カノンとボルタ
もうひとつ面白い例が、バッハ《音楽の捧げもの》の「螺旋カノン」(Canon per tonos)です。一周するごとに全音ずつ上へ転調していくので、絶対的な音の高さまで状態に含めれば、状態は無限に増えていきます。
「上限のない記憶、あるじゃん！」と思うかもしれません。でも、この「音の高さ」というカウンタは増え続けるだけで、楽譜にはその値を読んで分岐する仕組みがありません。第2節で見たとおり、上限のない記憶と、それを見て分岐する仕組みは両方必要です。片方だけでは届きません。
3.1節のボルタと並べると、ちょうど対になっています。
| 上限のない記憶 | 記憶を見た分岐 | |
|---|---|---|
| ボルタ | ×(回数は楽譜に書かれた定数) | ○ |
| 螺旋カノン | ○(音の高さが上がり続ける) | × |
| 2カウンタ機械 | ○ | ○ |
楽譜には、2つの材料がそれぞれ片方ずつしかないわけです。
5. 「可能な限り遅く」みたいな自由な指示は？
楽譜の世界には、もっと自由な指示もあります。有名なのが、ジョン・ケージ《ORGAN²/ASLSP》(As SLow aS Possible、可能な限り遅く)です。ドイツのハルバーシュタットの教会では、この曲を2001年から639年かけて演奏する計画が進んでいます。
こういう指示が入ると、話は変わるのでしょうか。指示の種類ごとに考えてみます。
5.1 時間についての自由(テンポ・音の長さ)
「可能な限り遅く」が自由にするのは、各音をいつ鳴らすかです。何を、どの順で鳴らすかは変わりません。
演奏を「音の列 $w$」と「各音を鳴らす時刻 $t$」の組 $(w, t)$ と見ると、テンポの指示が動かすのは $t$ だけです。639年かかる演奏も数十分で終わる演奏も、$w$ としては同じ列です。計算に関わるのは $w$ のほうなので、計算能力は変わりません。
5.2 順番についての自由(開かれた形式)
シュトックハウゼン《クラヴィーア曲 XI》のように、断片をどの順で弾くかを演奏者が選ぶ作品もあります。これは数学的には、非決定性を足すことにあたります。
しかし、状態が有限のまま非決定性を足しても、決定的な有限オートマトンと同じ能力にしかなりません(部分集合構成)。やはり計算能力は増えません。
5.3 言葉による自由(テキスト・スコア)
いちばん強力なのは、指示そのものを自然言語で書く作品です(フルクサスのイベント・スコアなど)。これを認めると「このチューリング機械を手で実行せよ」と書けてしまうので、チューリング完全性は自明に達成されます。
ただしこの場合、計算しているのは楽譜ではなく、文章を読んで実行する演奏者です。「プログラムのコメント欄に手順を書いておけば、読んだ人間が実行してくれる」と言っているのと同じで、記法の性質としては意味がありません。この記事が五線譜の記号に話を絞っているのは、このためです。
| 指示の種類 | 例 | 何が変わるか | 計算能力 |
|---|---|---|---|
| 時間 | ASLSP, フェルマータ | 鳴らす時刻だけ | 変わらない |
| 順番 | 《クラヴィーア曲 XI》 | 非決定性が入る | 有限オートマトン止まり |
| 無限反復 | 無限カノン | 終わらなくなる | 有限オートマトン止まり |
| 言葉 | テキスト・スコア | 演奏者に丸投げ | 自明にTC(記法の性質ではない) |
6. おまけ:チューリング完全な楽譜を作るには
逆に、五線譜に何を足せばチューリング完全になるのでしょうか。第2節の Minsky の定理から、次の2つを足せば十分です。
- カウンタ記号:「カウンタ $X$ を1増やす」「1減らす」という記号。カウンタは $X$ と $Y$ の2つあれば足りる。
- 条件つきボルタ:「$X = 0$ なら1番括弧、そうでなければ2番括弧」という括弧。
見方を変えると、これは既存のボルタの改造です。ボルタはもともと、カウンタを見て分岐する記号でした。それが見るカウンタを、「反復区間に縛られた上限つきの周回数」から「上限がなく、どこからでも増減できる変数 $X, Y$」に差し替える。たったそれだけで、楽譜は2カウンタ機械を書けるようになり、チューリング完全になります。
ただ、この楽譜を渡された演奏者は、弾きながら2つの数を頭の中で管理し続けなければなりません。標準の五線譜がそうなっていないのは、演奏者にやさしい設計だと言えそうです。
まとめ
- 楽譜は、ループ(反復)・分岐(ボルタ)・goto(D.C.)を持つ、プログラムっぽい記法である。
- ボルタという「カウンタを見た分岐」は持っているが、そのカウンタには楽譜に書かれた回数という上限がある。演奏中に自由に増減できる変数がないため、状態は有限通りしかない。
- 標準的な慣習では、演奏は必ず終わる。無限ループを許しても、状態が有限なので停止は判定できる。どちらにしても、チューリング完全ではない。
- 無限ループする演奏は最終周期的な列にしかならない。素数のリズムは最終周期的でないので、演奏者に選択を委ねない限り、どんな楽譜でも鳴らせない。
- テンポや演奏順の自由は、計算能力を増やさない。自然言語の指示を認めればチューリング完全になるが、それは演奏者の能力である。
- チューリング完全にするには、ボルタが見るカウンタを「上限がなく、どこからでも増減できる変数」に差し替えればよい(2つで足りる)。
最後に、冒頭の問いに答えておきます。エラトステネスの篩は、「採譜」できません。100拍目までのような有限の範囲なら素数のリズムを書けますが、それは計算した答えを写しているだけです。篩そのものを楽譜にしようとすると、見つけた素数を覚えておく場所が、五線譜のどこにもないのです。
おまけ:実在する「楽譜プログラミング言語」
「楽譜でプログラムを書く」というアイデアは、難解プログラミング言語(esolang)の世界ですでに形になっています。本記事の議論から見ると、どちらも「楽譜に上限のない記憶を足した言語」として読めます。
Scorlang
2010年にブログ「ならば」で提案された、五線譜の見た目でプログラムを書く言語です。仕様の要点は次のとおりです。
- 音符は、音名の値(C〜G を十七進法の数字とみなした 10〜16)をスタックに積む命令。オクターブごとに別のスタックがある
- シャープ・フラットは、スタックの値との足し算・引き算
- 休符は、値を文字コードとみなして出力する命令
- 反復記号は C 言語の while 文。「スタックの値が 0 でない間」繰り返す
本記事の言葉で言えば、反復記号の意味を「書かれた回数だけ繰り返す」から「データが 0 になるまで繰り返す」に変えています。つまり、分岐の判断が、上限のない記憶(スタック)を見るようになっているわけです。第6節で考えた「ボルタが見るカウンタを差し替える」改造が、反復記号の側で実現されています。
作者自身は「Scorlangはチューリング完全だと思う（願望）」と書いていて、処理系は公開されていません。仕様を読む限り、フラットを2回重ねると値を1増やしたり減らしたりできます(例:A♭ で $10 - y$、続けて同じオクターブの B♭ で $11 - (10 - y) = y + 1$)。2つのオクターブのスタックをカウンタとして使えば、2カウンタ機械が組めそうです。ただし、筆者は細部までは検証していません。
Velato
Daniel Temkin が2009年に作った言語で、プログラムは MIDI ファイルです。最初に鳴った音を「コマンドの基音」とし、そこからの音程(長2度、短3度など)で命令が決まります。変数の宣言・代入、while ループ、if 文などが音程で書けて、Esolang wiki ではチューリング完全な言語とされています。
Velato がプログラムにするのは、五線譜の記号ではなく音そのもの(音高と順序)です。そのため、反復記号や D.C. といった記譜上の制約とは無関係で、変数という上限のない記憶を最初から持っています。命令が音程で決まるため、ジャズ風の響きのプログラムになりやすい、という特徴もあるそうです。
本記事との関係
| 素材 | 上限のない記憶 | 記憶を見た分岐 | チューリング完全 | |
|---|---|---|---|---|
| 標準の五線譜 | 五線譜の記号 | × | ○(ボルタ) | × |
| Scorlang | 五線譜の記号(意味を変更) | ○(スタック) | ○(反復記号 = while) | おそらく○(未検証) |
| Velato | 音高と順序(MIDI) | ○(変数) | ○(while, if) | ○ |
どちらの言語も、楽譜や音の見た目は借りつつ、本記事で「足りない」とした上限のない記憶を、言語仕様として足しています。裏を返せば、そこを足さない限り、楽譜はプログラミング言語になれないということです。
参考文献
- M. L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
- naraba, 「楽譜でプログラミングする言語Scorlang」, ならば, 2010. https://naraba.hatenablog.com/entry/20100530/p1
- 「Velato」, Esolang wiki. https://esolangs.org/wiki/Velato
