FRACTRANのソースを表示

'''FRACTRAN'''（フラクトラン）は[[チューリング完全]]な[[難解プログラミング言語]]で、数学者[[ジョン・コンウェイ]]によって開発された。この言語で書かれたプログラムは、正の整数''n''を初期値として持つ正の[[分数]]の[[列 (数学)|列]]である。プログラムは、以下のように整数''n''を更新することによって実行される。

# ''nf''が整数となるようなリスト内の最初の分数''f''において、''n''を''nf''に置換する。
# nをかけて整数となるような分数がリスト内になくなるまでこれを繰り返し、停止する。

{{Harvnb|Conway|1987}}には、PRIMEGAME（素数ゲーム）と呼ばれる、連続する[[素数]]を探索する以下のFRACTRANプログラムがある。<math display="block">\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right)</math>''n''=2として始め、このFRACTRANプログラムは以下の整数列を生成する。
* 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... （{{OEIS|id=A007542}}）

2の後、この数列は以下の2の[[冪乗]]を含む。<math display="block">2^2=4,\, 2^3=8,\, 2^5=32,\, 2^7=128,\, 2^{11}=2048,\, 2^{13}=8192,\, 2^{17}=131072,\, 2^{19}=524288,\,  \dots</math>（{{OEIS|id=A034785}}）

これらの2のべき乗の[[指数]]部分は2, 3, 5, …というような素数である。 

== FRACTRANプログラムを理解する ==
FRACTRANプログラムはレジスタが引数''n''の素数指数として格納される[[レジスタマシン]]として見ることができる。

[[ゲーデル数]]を用いて、正の整数''n''は任意の数の任意の大きさの正の整数の[[変数 (プログラミング)|変数]]を[[符号化]]することができる<ref group="注釈">[[Gödel numbering]] [[ゲーデル数]]は、慣例が適用して、直接負の整数、浮動小数点数や文字列を間接的に表すようにすることはできるが、直接的に使用することはできない。FRACTRANに提案されている拡張機能には[http://www.esolangs.org/wiki/Fractran_plus_plus FRACTRAN++]<small>（Written in English）</small>及び[http://home.nvg.org/~oerjan/esoteric/bag/ Bag]<small>（Written in English）</small>などがある。</ref>。 各変数の値は、整数の[[素因数分解]]によって素数のべき乗に符号化される。例えば、整数<math display="block">60 = 2^2 \times 3^1 \times 5^1</math>は、レジスタの状態が以下のようになっていることを表す。
* ある変数（これをv2とする）の値が2である。
* ほかの変数の2つ（これをv3とv5とする）の値が1である。
* ほかの全ての変数の値が0である。

FRACTRANプログラムは、正の分数の列である。すべての分数はそれぞれ、1つ以上の変数をテストする命令を表し、それはその[[分母]]の[[素因数]]によって表される。例えば、<math display="block">f_1 = \frac{21}{20} = \frac{3 \times 7}{2^2 \times 5^1}</math>はv2とv5を評価する。<math>v_2 \ge 2</math> かつ <math>v_5 \ge 1</math>のとき、v2から2を、v5から1をそれぞれ引き、v3に1を、v7に1を加える。以下に例を挙げる。<math display="block">60 \cdot f_1 = 2^2 \times 3^1 \times 5^1 \cdot \frac{3 \times 7}{2^2 \times 5^1} = 3^2 \times 7^1</math>FRACTRANプログラムは分数のリストに過ぎず、これらの評価・演算命令（加算・減算命令）はFRACTRAN言語において唯一許された命令である。さらに、以下の制約が適用される。
* 命令が実行されるごとに、評価される変数は[[デクリメント|デクリメント（減算）]]される。
* 同じ変数に対して、1つの命令で[[インクリメント|インクリメント（加算）]]と[[デクリメント|デクリメント（減算）]]を両方することはできない。（そうでなければ、その命令を表す分数が[[既約分数]]にならない。）したがって、すべてのFRACTRANの命令は変数の評価においてその変数を消費する。
* FRACTRANの命令は、変数が[[0]]かどうかを直接評価することはできない。（しかし、既定の命令を作成して、それを特定の変数を評価する別の命令の後に配置することで、間接的な評価は可能である。）

== 簡単なプログラムの作成 ==

=== [[加算]] ===
最も単純なFRACTRANプログラムは以下の1つの命令である。<math display="block">\left( \frac{3}{2} \right)</math>このプログラムは以下の単純な[[アルゴリズム]]に表される。
{| class="wikitable"
!FRACTRAN<br />命令
!条件
!アクション
|-
| align="center" |<math>\frac{3}{2}</math>
|v2 > 0
|v2から1を引き、v3に1を加える
|-
|
|v2 = 0
|停止する
|}
<math>2^a 3^b</math>の形で与えられた初期値に対し、このプログラムは以下の数列を計算する。

<math>2^{a-1} 3^{b+1}</math>, <math>2^{a-2} 3^{b+2}</math>, …

これを<math>a</math>ステップ行い、最終的に2で割り切れなくなり、<math>\frac{3}{2}</math>をかけても整数とならなくなったとき、レジスタマシンは<math> 3^{a + b} </math>を出力して停止する。これにより、2つの整数が加算される。

=== [[乗算]] ===
「乗算器」は、「加算器」を「ループする」ことで作ることができる。これには、アルゴリズムに[[State パターン|State]]（[[オブジェクト指向プログラミング]]における[[デザインパターン (ソフトウェア)|デザインパターン]]の1つ）を導入する必要がある。このアルゴリズムは<math>2^a 3^b</math>を引数に取り、<math>5^{ab}</math>を生成する。
{| class="wikitable"
!State
!条件
!アクション
!次のState
|-
| rowspan="4" align="center" |A
|v7 > 0
|v7から1を引き、v3に1を加える
| align="center" |A
|-
|v7 = 0 かつ<br />v2 > 0
|v2から1を引く
| align="center" |B
|-
|v7 = 0 かつ<br />v2 = 0 かつ<br />v3 > 0
|v3から1を引く
| align="center" |A
|-
|v7 = 0 かつ<br />v2 = 0 かつ<br />v3 = 0
|停止する
|
|-
| rowspan="2" align="center" |B
|v3 > 0
|v3から1を引き、v5とv7にそれぞれ1を加える
| align="center" |B
|-
|v3 = 0
|なし
| align="center" |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インジケータと命令を追加すると以下のようになる。
{| class="wikitable"
!FRACTRAN<br />命令
!State
!State<br />インジケータ
!条件
!アクション
!次のState
|-
| align="center" |<math>\frac{3}{7}</math>
| rowspan="4" align="center" |A
| rowspan="4" |なし
|v7 > 0
|v7から1を引き、v3に1を加える
| align="center" |A
|-
| align="center" |<math>\frac{11}{2}</math>
|v7 = 0
かつ v2 > 0
|v2から1を引く
| align="center" |B
|-
| align="center" |<math>\frac{1}{3}</math>
|v7 = 0 
かつv2 = 0 かつv3 > 0
|v3から1を引く
| align="center" |A
|-
|
|v7 = 0 <br />かつv2 = 0 かつ<br />v3 = 0
|停止する
|
|-
| align="center" |<math>\frac{5 \cdot 7 \cdot 13}{3 \cdot 11}, \frac{11}{13}</math>
| rowspan="2" align="center" |B
| rowspan="2" |v11, v13
|v3 > 0
|v3から1を引き、v5とv7にそれぞれ1を加える
| align="center" |B
|-
| align="center" |<math>\frac{1}{11}</math>
|v3 = 0
|なし
| align="center" |A
|}
FRACTRAN命令を書き出すとき、最後にAのStateの命令が必要になる。AのStateにはインジケータがないからである。Stateインジケータが設定されていないのが既定のStateである。ゆえに、乗算器のFRACTRANプログラムは以下のようになる。<math display="block">\left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{3} \right)</math>入力2<sup>''a''</sup>3<sup>''b''</sup>に対してこのプログラムは5<sup>''ab''</sup>を出力する<ref group="注釈">[http://www.esolangs.org/wiki/Fractran Esolang FRACTRAN page]<small>（Written in English）</small>に類似した乗算器のアルゴリズムの説明がある。</ref>。 [[ファイル:FRACTRANmult0.gif|中央|サムネイル|544x544ピクセル|上記のFRACTRANプログラムで3×2を計算する（3×2は6であるから、入力は<math>2^3\times 3^2=72</math>で、出力は<math>5^6=15625</math>となる）]]

=== [[減算]]と[[除算]] ===
同様に、FRACTRAN「減算器」を作ることができる。さらに、減算を繰り返すことで、以下の「商とあまり」のアルゴリズムを作ることもできる。
{| class="wikitable"
!FRACTRAN<br />命令
!State
!State<br />インジケータ
!条件
!アクション
!次のState
|-
| align="center" |<math>\frac{7 \cdot 13}{2 \cdot 3 \cdot 11}, \frac{11}{13}</math>
| rowspan="3" align="center" |A
| rowspan="3" |v11, v13
|v2 > 0 かつ<br />v3 > 0
|v2とv3からそれぞれ1を引き、v7に1を加える
| align="center" |A
|-
| align="center" |<math>\frac{1}{3 \cdot 11}</math>
|v2 = 0 かつ<br />v3 > 0
|v3から1を引く
| align="center" |X
|-
| align="center" |<math>\frac{5 \cdot 17}{11}</math>
|v3 = 0
|v5に1を加える
| align="center" |B
|-
| align="center" |<math>\frac{3 \cdot 19}{7 \cdot 17}, \frac{17}{19}</math>
| rowspan="2" align="center" |B
| rowspan="2" |v17, v19
|v7 > 0
|v7から1を引き、v3に1を加える
| align="center" |B
|-
| align="center" |<math>\frac{11}{17}</math>
|v7 = 0
|なし
| align="center" |A
|-
| align="center" |<math>\frac{1}{3}</math>
| rowspan="2" align="center" |X
| rowspan="2" |
|v3 > 0
|v3から1を引く
| align="center" |X
|-
|
|v3 = 0
|停止する
|
|}
FRACTRANプログラムに書き出すと、以下のようになる。<math display="block">\left( \frac{91}{66}, \frac{11}{13}, \frac{1}{33}, \frac{85}{11}, \frac{57}{119}, \frac{17}{19}, \frac{11}{17}, \frac{1}{3} \right)</math>入力2<sup>''n''</sup>3<sup>''d''</sup>11に対して、このプログラムは5<sup>''q''</sup>7<sup>''r''</sup>を出力する。ここに、''n'' = ''qd'' + ''r'' かつ 0 ≤ ''r''  < ''d''である。

== コンウェイの素数アルゴリズム ==
コンウェイの素数生成アルゴリズム（前述）は本質的に、２つのループ内の商とあまりのアルゴリズムである。<math>2^n 7^m</math>（ただし0 ≤ ''m''  < ''n''）の形で与えられた入力に対し、アルゴリズムは''n''+1の最大の約数''k''を見つけるまで''n''+1を''n''から1までの整数でそれぞれ割ろうとする。そして2<sup>''n''+1</sup> 7<sup>''k''-1</sup>を返し、繰り返す。このアルゴリズムで生成されるStateの番号の列はkが1のとき2のべき乗を生成する（7の指数は0になる）のは、2の指数が素数のときのみである。Havil (2007)に、コンウェイのアルゴリズムの段階的な説明がある。

このプログラムにおいて、素数2, 3, 5, 7 ... を得るには、それぞれ19, 69, 281, 710, ...のステップが必要となる。（{{OEIS|id=A007547}}）

コンウェイのプログラムには前述のものより分数が2つ異なる版も存在する<ref>{{Harvnb|Guy|1983|p=26}}; {{Harvnb|Conway|Guy|1996|p=147}}</ref>。<math display="block">\left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right)</math>こちらの方が少し速い。2, 3, 5, 7... を得るのには19, 69, 280, 707... のステップが必要である。（{{OEIS|id=A007546}}）このプログラムの特定の整数''N''が素数であるか調べる反復には、以下の数のステップが必要である。<math display="block">N - 1 + (6N+2)(N-b) + 2 \sum\limits^{N-1}_{d=b} \left\lfloor \frac{N}{d} \right\rfloor</math>このとき、<math>b < N</math>は最大の''N''の整数の約数であり、<math>\lfloor x \rfloor</math>は[[床関数と天井関数|床関数]]である<ref>{{Harvnb|Guy|1983|p=33}}</ref>。


以下は、1999年の、Devin Kilminsterによる、これより少し短い、10の命令からなるプログラムである<ref>{{Harvnb|Havil|2007|p=176}}</ref>。<math display="block">\left( \frac{7}{3}, \frac{99}{98}, \frac{13}{49}, \frac{39}{35}, \frac{36}{91}, \frac{10}{143}, \frac{49}{13}, \frac{7}{11}, \frac{1}{2}, \frac{91}{1} \right)</math>初期値''n'' = 10において、連続した素数が後続する10のべき乗によって生成される。 
== 他の例 ==
以下のFRACTRANプログラム<math display="block">\left( \frac{3 \cdot 11}{2^2 \cdot 5} , \frac{5}{11}, \frac{13}{2 \cdot 5}, \frac{1}{5}, \frac{2}{3}, \frac{2 \cdot 5}{7}, \frac{7}{2} \right)</math>つまり<math>\left(\frac{20}{33},\frac 5{11},\frac{13}{10},\frac 15,\frac 23,\frac{10}7,\frac 72\right)</math>
は、2進記数法における''a''の[[ハミング重み]] H(''a'')、すなわち''a''の[[2進数]]表記における[[1]]の個数を計算する。入力は2<sup>''a''</sup>で出力13<sup>H(''a'')</sup>である。<ref>John Baez, [http://golem.ph.utexas.edu/category/2006/10/puzzle_4.html Puzzle #4], The ''n''-Category Café</ref>このプログラムを解析すると以下のようになる。
{| class="wikitable"
!FRACTRAN<br />命令
!State
!State<br />インジケータ
!条件
!アクション
!次のState
|-
| align="center" |<math>\frac{3 \cdot 11}{2^2 \cdot 5}, \frac{5}{11}</math>
| rowspan="3" align="center" |A
| rowspan="3" |v5, v11
|v2 > 1
|v2から2を引き、v3に1を加える
| align="center" |A
|-
| align="center" |<math>\frac{13}{2 \cdot 5}</math>
|v2 = 1
|v2から1を引き、v13に1を加える
| align="center" |B
|-
| align="center" |<math>\frac{1}{5}</math>
|v2 = 0
|なし
| align="center" |B
|-
| align="center" |<math>\frac{2}{3}</math>
| rowspan="4" align="center" |B
| rowspan="4" |None
|v3 > 0
|v3から1を引き、v2に1を加える
| align="center" |B
|-
| align="center" |<math>\frac{2 \cdot 5}{7}</math>
|v3 = 0 かつ<br />v7 > 0
|v7から1を引き、v2に1を加える
| align="center" |A
|-
| align="center" |<math>\frac{7}{2}</math>
|v3 = 0 かつ<br />v7 = 0 かつ<br />v2 > 0
|v2から1を引き、v7に1を加える
| align="center" |B
|-
|
|v2 = 0 かつ<br />v3 = 0 かつ<br />v7 = 0
|停止する
|
|}

== 注釈 ==

{{Reflist||group=注釈}}

== 関連項目 ==

* [[OISC]]
* [[コラッツの問題]]

== 参考資料 ==
{{Reflist}} {{refbegin}}
*{{cite journal|last=Guy|first=Richard K.|author-link=Richard Kenneth Guy|year=1983|title=Conway's Prime Producing Machine|url=https://www.tandfonline.com/doi/abs/10.1080/0025570X.1983.11977011|journal=[[Mathematics Magazine]]|volume=56|issue=1|pages=26–33|publisher=[[Taylor & Francis]]|doi=10.1080/0025570X.1983.11977011|ref=harv}}
*{{cite journal|last=Conway|first=John H.|year=1987|title=FRACTRAN: A simple universal programming language for arithmetic|journal=Open Problems in Communication and Computation|pages=4–26|publisher=Springer-Verlag New York, Inc.|doi=10.1007/978-1-4612-4808-8_2|isbn=978-1-4612-9162-6|ref=harv}}
* {{cite book |last=Conway |first=John H. |last2=Guy |first2=Richard K. |title=The Book of Numbers |publisher=Springer-Verlag New York, Inc. |year=1996 |isbn=0-387-97993-X |url-access=registration |url=https://archive.org/details/bookofnumbers0000conw|ref=harv}}
*{{cite book |last=Havil |first=Julian |title=Nonplussed! |publisher=Princeton University Press |year=2007 |isbn=978-0-691-12056-0 |url-access=registration |url=https://archive.org/details/nonplussedmathem00havi|ref=harv}}
*{{cite book |title=Genius At Play - The Curious Mind of John Horton Conway |last=Roberts |first=Siobhan |author-link=Siobhan Roberts |chapter=Criteria of virtue |pages=115–119 |publisher=Bloomsbury |year=2015 |isbn=978-1-62040-593-2}}
{{refend}}

== 外部リンク ==

* [https://www.uctv.tv/shows/Fractran-A-Ridiculous-Logical-Language-with-John-Conway-23320 Lecture from John Conway: "Fractran: A Ridiculous Logical Language"]
* [http://scienceblogs.com/goodmath/2006/10/27/prime-number-pathology-fractra/ "Prime Number Pathology: Fractran"]
* <templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>{{MathWorld|title=FRACTRAN}}
* [http://brainwagon.org/?p=2207 ''Prime Number Pathology'']
* [http://www.esolangs.org/wiki/Fractran FRACTRAN] - (Esolang wiki)
* [https://web.archive.org/web/20130125232746/http://www.dev.gd/20130121-fun-with-john-conways-fractran.html Ruby implementation and example programs]
* [https://projecteuler.net/problem=308 Project Euler Problem 308]
* [http://malisper.me/2016/06/11/building-fizzbuzz-fractran-bottom/ "Building Fizzbuzz in Fractran from the Bottom Up"]
* [https://web.archive.org/web/20180104084828/http://clomont.com/a-universal-fractran-interpreter-in-fractran/ Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"]

{{DEFAULTSORT:ふらくとらん}}
[[Category:レクリエーション数学]]
[[Category:難解プログラミング言語]]
[[Category:計算モデル]]