FRACTRAN
FRACTRAN(フラクトラン)はチューリング完全な難解プログラミング言語で、数学者ジョン・コンウェイによって開発された。この言語で書かれたプログラムは、正の整数nを初期値として持つ正の分数の列である。プログラムは、以下のように整数nを更新することによって実行される。
- nfが整数となるようなリスト内の最初の分数fにおいて、nをnfに置換する。
- nをかけて整数となるような分数がリスト内になくなるまでこれを繰り返し、停止する。
Conway 1987には、PRIMEGAME(素数ゲーム)と呼ばれる、連続する素数を探索する以下のFRACTRANプログラムがある。
- 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (オンライン整数列大辞典の数列 A007542)
2の後、この数列は以下の2の冪乗を含む。
これらの2のべき乗の指数部分は2, 3, 5, …というような素数である。
FRACTRANプログラムを理解する
編集FRACTRANプログラムはレジスタが引数nの素数指数として格納されるレジスタマシンとして見ることができる。
ゲーデル数を用いて、正の整数nは任意の数の任意の大きさの正の整数の変数を符号化することができる。[注釈 1] 各変数の値は、整数の素因数分解によって素数のべき乗に符号化される。例えば、整数
- ある変数(これをv2とする)の値が2である。
- ほかの変数の2つ(これをv3とv5とする)の値が1である。
- ほかの全ての変数の値が0である。
FRACTRANプログラムは、正の分数の列である。すべての分数はそれぞれ、1つ以上の変数をテストする命令を表し、それはその分母の素因数によって表される。例えば、
- 命令が実行されるごとに、評価される変数はデクリメント(減算)される。
- 同じ変数に対して、1つの命令でインクリメント(加算)とデクリメント(減算)を両方することはできない。(そうでなければ、その命令を表す分数が既約分数にならない。)したがって、すべてのFRACTRANの命令は変数の評価においてその変数を消費する。
- FRACTRANの命令は、変数が0かどうかを直接評価することはできない。(しかし、既定の命令を作成して、それを特定の変数を評価する別の命令の後に配置することで、間接的な評価は可能である。)
簡単なプログラムの作成
編集最も単純なFRACTRANプログラムは以下の1つの命令である。
FRACTRAN 命令 |
条件 | アクション |
---|---|---|
v2 > 0 | v2から1を引き、v3に1を加える | |
v2 = 0 | 停止する |
の形で与えられた初期値に対し、このプログラムは以下の数列を計算する。
, , …
これを ステップ行い、最終的に2で割り切れなくなり、 をかけても整数とならなくなったとき、レジスタマシンは を出力して停止する。これにより、2つの整数が加算される。
「乗算器」は、「加算器」を「ループする」ことで作ることができる。これには、アルゴリズムにState(オブジェクト指向プログラミングにおけるデザインパターンの1つ)を導入する必要がある。このアルゴリズムは を引数に取り、 を生成する。
State | 条件 | アクション | 次のState |
---|---|---|---|
A | v7 > 0 | v7から1を引き、v3に1を加える | A |
v7 = 0 かつ v2 > 0 |
v2から1を引く | B | |
v7 = 0 かつ v2 = 0 かつ v3 > 0 |
v3から1を引く | A | |
v7 = 0 かつ v2 = 0 かつ v3 = 0 |
停止する | ||
B | v3 > 0 | v3から1を引き、v5とv7にそれぞれ1を加える | B |
v3 = 0 | なし | A |
BのStateはv3とv5を加算しv3をv7に値を移すループである。また、AのStateは、BのStateをv2回繰り返す外側の制御ループである。AのStateはまた、BのStateのループが完了した後、v7からv3に値を移す(つまり、v3から一度v7に移動して、またv3に戻る)。
新しい変数をStateインジケータとして用いることで、Stateを実行することができる。B用のStateインジケータはv11とv13である。ここで、1つのループにState制御インジケータは第一のフラグ(v11)と第二のフラグ(v13)の2つが必要となることに留意されたい。なぜなら、それぞれのインジケータは評価されると消費されるため、「現在のStateを継続せよ」と言うために第二のインジケータが必要となるからである。この第二のインジケータは、次の命令で第一のインジケータに還元され、ループが継続する。
乗算アルゴリズムの表にFRACTRAN Stateインジケータと命令を追加すると以下のようになる。
FRACTRAN 命令 |
State | State インジケータ |
条件 | アクション | 次のState |
---|---|---|---|---|---|
A | なし | v7 > 0 | v7から1を引き、v3に1を加える | A | |
v7 = 0
かつ v2 > 0 |
v2から1を引く | B | |||
v7 = 0
かつv2 = 0 かつv3 > 0 |
v3から1を引く | A | |||
v7 = 0 かつv2 = 0 かつ v3 = 0 |
停止する | ||||
B | v11, v13 | v3 > 0 | v3から1を引き、v5とv7にそれぞれ1を加える | B | |
v3 = 0 | なし | A |
FRACTRAN命令を書き出すとき、最後にAのStateの命令が必要になる。AのStateにはインジケータがないからである。Stateインジケータが設定されていないのが既定のStateである。ゆえに、乗算器のFRACTRANプログラムは以下のようになる。
同様に、FRACTRAN「減算器」を作ることができる。さらに、減算を繰り返すことで、以下の「商とあまり」のアルゴリズムを作ることもできる。
FRACTRAN 命令 |
State | State インジケータ |
条件 | アクション | 次のState |
---|---|---|---|---|---|
A | v11, v13 | v2 > 0 かつ v3 > 0 |
v2とv3からそれぞれ1を引き、v7に1を加える | A | |
v2 = 0 かつ v3 > 0 |
v3から1を引く | X | |||
v3 = 0 | v5に1を加える | B | |||
B | v17, v19 | v7 > 0 | v7から1を引き、v3に1を加える | B | |
v7 = 0 | なし | A | |||
X | v3 > 0 | v3から1を引く | X | ||
v3 = 0 | 停止する |
FRACTRANプログラムに書き出すと、以下のようになる。
コンウェイの素数アルゴリズム
編集コンウェイの素数生成アルゴリズム(前述)は本質的に、2つのループ内の商とあまりのアルゴリズムである。 (ただし0 ≤ m < n)の形で与えられた入力に対し、アルゴリズムはn+1の最大の約数kを見つけるまでn+1をnから1までの整数でそれぞれ割ろうとする。そして2n+1 7k-1を返し、繰り返す。このアルゴリズムで生成されるStateの番号の列はkが1のとき2のべき乗を生成する(7の指数は0になる)のは、2の指数が素数のときのみである。Havil (2007)に、コンウェイのアルゴリズムの段階的な説明がある。
このプログラムにおいて、素数2, 3, 5, 7 ... を得るには、それぞれ19, 69, 281, 710, ...のステップが必要となる。(オンライン整数列大辞典の数列 A007547)
コンウェイのプログラムには前述のものより分数が2つ異なる版も存在する。[1]
以下は、1999年の、Devin Kilminsterによる、これより少し短い、10の命令からなるプログラムである。[3]
他の例
編集以下のFRACTRANプログラム
FRACTRAN 命令 |
State | State インジケータ |
条件 | アクション | 次のState |
---|---|---|---|---|---|
A | v5, v11 | v2 > 1 | v2から2を引き、v3に1を加える | A | |
v2 = 1 | v2から1を引き、v13に1を加える | B | |||
v2 = 0 | なし | B | |||
B | None | v3 > 0 | v3から1を引き、v2に1を加える | B | |
v3 = 0 かつ v7 > 0 |
v7から1を引き、v2に1を加える | A | |||
v3 = 0 かつ v7 = 0 かつ v2 > 0 |
v2から1を引き、v7に1を加える | B | |||
v2 = 0 かつ v3 = 0 かつ v7 = 0 |
停止する |
注釈
編集- ^ Gödel numbering ゲーデル数は、慣例が適用して、直接負の整数、浮動小数点数や文字列を間接的に表すようにすることはできるが、直接的に使用することはできない。FRACTRANに提案されている拡張機能にはFRACTRAN++(Written in English)及びBag(Written in English)などがある。
- ^ Esolang FRACTRAN page(Written in English)に類似した乗算器のアルゴリズムの説明がある。
関連項目
編集参考資料
編集- ^ Guy 1983, p. 26; Conway & Guy 1996, p. 147
- ^ Guy 1983, p. 33
- ^ Havil 2007, p. 176
- ^ John Baez, Puzzle #4, The n-Category Café
- Guy, Richard K. (1983). “Conway's Prime Producing Machine”. Mathematics Magazine (Taylor & Francis) 56 (1): 26–33. doi:10.1080/0025570X.1983.11977011 .
- Conway, John H. (1987). “FRACTRAN: A simple universal programming language for arithmetic”. Open Problems in Communication and Computation (Springer-Verlag New York, Inc.): 4–26. doi:10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6.
- Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc.. ISBN 0-387-97993-X
- Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 978-0-691-12056-0
- Roberts, Siobhan (2015). “Criteria of virtue”. Genius At Play - The Curious Mind of John Horton Conway. Bloomsbury. pp. 115–119. ISBN 978-1-62040-593-2
外部リンク
編集- Lecture from John Conway: "Fractran: A Ridiculous Logical Language"
- "Prime Number Pathology: Fractran"
- Weisstein, Eric W. "FRACTRAN". mathworld.wolfram.com (英語).
- Prime Number Pathology
- FRACTRAN - (Esolang wiki)
- Ruby implementation and example programs
- Project Euler Problem 308
- "Building Fizzbuzz in Fractran from the Bottom Up"
- Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"