FRACTRAN
): 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. https://archive.org/details/bookofnumbers0000conw
Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 978-0-691-12056-0. https://archive.org/details/nonplussedmathem00havi
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
FRACTRANプログラムはレジスタが引数nの素数指数として格納されるレジスタマシンとして見ることができる。
ゲーデル数を用いて、正の整数nは任意の数の任意の大きさの正の整数の変数を符号化することができる。 各変数の値は、整数の素因数分解によって素数のべき乗に符号化される。例えば、整数
は、レジスタの状態が以下のようになっていることを表す。
ある変数(これをv2とする)の値が2である。
ほかの変数の2つ(これをv3とv5とする)の値が1である。
ほかの全ての変数の値が0である。
FRACTRANプログラムは、正の分数の列である。すべての分数はそれぞれ、1つ以上の変数をテストする命令を表し、それはその分母の素因数によって表される。例えば、
はv2とv5を評価する。 v 2 ≥ 2 {\displaystyle v_{2}\geq 2} かつ v 5 ≥ 1 {\displaystyle v_{5}\geq 1} のとき、v2から2を、v5から1をそれぞれ引き、v3に1を、v7に1を加える。
以下に例を挙げる。
FRACTRANプログラムは分数のリストに過ぎず、これらの評価・演算命令(加算・減算命令)はFRACTRAN言語において唯一許された命令である。さらに、以下の制約が適用される。
命令が実行されるごとに、評価される変数はデクリメント(減算)される。
同じ変数に対して、1つの命令でインクリメント(加算)とデクリメント(減算)を両方することはできない。(そうでなければ、その命令を表す分数が既約分数にならない。)したがって、すべてのFRACTRANの命令は変数の評価においてその変数を消費する。
FRACTRANの命令は、変数が0かどうかを直接評価することはできない。(しかし、既定の命令を作成して、それを特定の変数を評価する別の命令の後に配置することで、間接的な評価は可能である。)