FRACTRAN（フラクトラン） はチューリング完全 かんぜん な難解 なんかい 言語 げんご 数学 すうがく 者 しゃ ジョン・コンウェイ によって開発 かいはつ 言語 げんご 書 か 正 せい 整数 せいすう n を初期 しょき 値 ち 持 も 正 せい 分数 ぶんすう 列 れつ 以下 いか 整数 せいすう n を更新 こうしん 実行 じっこう
nf が整数 せいすう 内 ない 最初 さいしょ 分数 ぶんすう f において、n をnf に置換 ちかん nをかけて整数 せいすう 分数 ぶんすう 内 ない 繰 く 返 かえ 停止 ていし Conway 1987 には、PRIMEGAME（素数 そすう 呼 よ 連続 れんぞく 素数 そすう 探索 たんさく 以下 いか
(
17
91
,
78
85
,
19
51
,
23
38
,
29
33
,
77
29
,
95
23
,
77
19
,
1
17
,
11
13
,
13
11
,
15
2
,
1
7
,
55
1
)
{\displaystyle \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)}
n =2として始 はじ 以下 いか 整数 せいすう 列 れつ 生成 せいせい
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... （オンライン整数 せいすう 列 れつ 大 だい 辞典 じてん の数列 すうれつ A007542 ） 2の後 のち 数列 すうれつ 以下 いか 冪 べき 乗 じょう 含 ふく
2
2
=
4
,
2
3
=
8
,
2
5
=
32
,
2
7
=
128
,
2
11
=
2048
,
2
13
=
8192
,
2
17
=
131072
,
2
19
=
524288
,
…
{\displaystyle 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 }
オンライン整数 せいすう 列 れつ 大 だい 辞典 じてん の数列 すうれつ A034785 ）
これらの2のべき乗 じょう 指数 しすう 部分 ぶぶん 素数 そすう
FRACTRANプログラムはレジスタが引数 ひきすう n の素数 そすう 指数 しすう 格納 かくのう レジスタマシン として見 み
ゲーデル数 すう を用 もち 正 せい 整数 せいすう n は任意 にんい 数 かず 任意 にんい 大 おお 正 せい 整数 せいすう 変数 へんすう 符号 ふごう 化 か [注釈 ちゅうしゃく 各 かく 変数 へんすう 値 ね 整数 せいすう 素因数 そいんすう 分解 ぶんかい 素数 そすう 乗 じょう 符号 ふごう 化 か 例 たと 整数 せいすう
60
=
2
2
×
3
1
×
5
1
{\displaystyle 60=2^{2}\times 3^{1}\times 5^{1}}
状態 じょうたい 以下 いか 表 あらわ
ある変数 へんすう 値 ね
ほかの変数 へんすう 値 ね
ほかの全 すべ 変数 へんすう 値 ね FRACTRANプログラムは、正 せい 分数 ぶんすう 列 れつ 分数 ぶんすう 以上 いじょう 変数 へんすう 命令 めいれい 表 あらわ 分母 ぶんぼ 素因数 そいんすう 表 あらわ 例 たと
f
1
=
21
20
=
3
×
7
2
2
×
5
1
{\displaystyle f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}}
評価 ひょうか
v
2
≥
2
{\displaystyle v_{2}\geq 2}
v
5
≥
1
{\displaystyle v_{5}\geq 1}
引 ひ 加 くわ 以下 いか 例 れい 挙 あ
60
⋅
f
1
=
2
2
×
3
1
×
5
1
⋅
3
×
7
2
2
×
5
1
=
3
2
×
7
1
{\displaystyle 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}}
分数 ぶんすう 過 す 評価 ひょうか 演算 えんざん 命令 めいれい 加算 かさん 減算 げんざん 命令 めいれい 言語 げんご 唯一 ゆいいつ 許 ゆる 命令 めいれい 以下 いか 制約 せいやく 適用 てきよう
命令 めいれい 実行 じっこう 評価 ひょうか 変数 へんすう デクリメント（減算 げんざん される。同 おな 変数 へんすう 対 たい 命令 めいれい インクリメント（加算 かさん とデクリメント（減算 げんざん を両方 りょうほう 命令 めいれい 表 あらわ 分数 ぶんすう 既 すんで 約分 やくぶん 数 すう 命令 めいれい 変数 へんすう 評価 ひょうか 変数 へんすう 消費 しょうひ FRACTRANの命令 めいれい 変数 へんすう 0 かどうかを直接 ちょくせつ 評価 ひょうか 既定 きてい 命令 めいれい 作成 さくせい 特定 とくてい 変数 へんすう 評価 ひょうか 別 べつ 命令 めいれい 後 のち 配置 はいち 間接 かんせつ 的 てき 評価 ひょうか 可能 かのう 最 もっと 単純 たんじゅん 以下 いか 命令 めいれい
(
3
2
)
{\displaystyle \left({\frac {3}{2}}\right)}
以下 いか 単純 たんじゅん アルゴリズム に表 あらわ
FRACTRAN命令 めいれい
条件 じょうけん アクション
3
2
{\displaystyle {\frac {3}{2}}}
v2 > 0
v2から1を引 ひ 加 くわ
v2 = 0
停止 ていし
2
a
3
b
{\displaystyle 2^{a}3^{b}}
形 かたち 与 あた 初期 しょき 値 ち 対 たい 以下 いか 数列 すうれつ 計算 けいさん
2
a
−
1
3
b
+
1
{\displaystyle 2^{a-1}3^{b+1}}
2
a
−
2
3
b
+
2
{\displaystyle 2^{a-2}3^{b+2}}
これを
a
{\displaystyle a}
行 おこな 最終 さいしゅう 的 てき 割 わ 切 き
3
2
{\displaystyle {\frac {3}{2}}}
整数 せいすう
3
a
+
b
{\displaystyle 3^{a+b}}
出力 しゅつりょく 停止 ていし 整数 せいすう 加算 かさん
「乗算 じょうざん 器 き 加算 かさん 器 き 作 つく State （オブジェクト指向 しこう におけるデザインパターン の1つ）を導入 どうにゅう 必要 ひつよう
2
a
3
b
{\displaystyle 2^{a}3^{b}}
引数 ひきすう 取 と
5
a
b
{\displaystyle 5^{ab}}
生成 せいせい
State
条件 じょうけん アクション
次 つぎ
A
v7 > 0
v7から1を引 ひ 加 くわ
A
v7 = 0 かつ
v2から1を引 ひ
B
v7 = 0 かつ
v3から1を引 ひ
A
v7 = 0 かつ
停止 ていし
B
v3 > 0
v3から1を引 ひ 加 くわ
B
v3 = 0
なし
A
BのStateはv3とv5を加算 かさん 値 ね 移 うつ 回 かい 繰 く 返 かえ 外側 そとがわ 制御 せいぎょ 完了 かんりょう 後 のち 値 ね 移 うつ 一 いち 度 ど 移動 いどう 戻 もど
新 あたら 変数 へんすう インジケータ として用 もち 実行 じっこう 用 よう 制御 せいぎょ 第 だい 一 いち フラグ （v11）と第 だい 二 に 必要 ひつよう 留意 りゅうい 評価 ひょうか 消費 しょうひ 現在 げんざい 継続 けいぞく 言 い 第 だい 二 に 必要 ひつよう 第 だい 二 に 次 つぎ 命令 めいれい 第 だい 一 いち 還元 かんげん 継続 けいぞく
乗算 じょうざん 表 ひょう 命令 めいれい 追加 ついか 以下 いか
FRACTRAN命令 めいれい 書 か 出 だ 最後 さいご 命令 めいれい 必要 ひつよう 設定 せってい 既定 きてい 乗算 じょうざん 器 き 以下 いか
(
455
33
,
11
13
,
1
11
,
3
7
,
11
2
,
1
3
)
{\displaystyle \left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)}
入力 にゅうりょく a b 対 たい ab 出力 しゅつりょく [注釈 ちゅうしゃく
上記 じょうき 計算 けいさん 入力 にゅうりょく
2
3
×
3
2
=
72
{\displaystyle 2^{3}\times 3^{2}=72}
出力 しゅつりょく
5
6
=
15625
{\displaystyle 5^{6}=15625}
同様 どうよう 減算 げんざん 器 き 作 つく 減算 げんざん 繰 く 返 かえ 以下 いか 商 しょう 作 つく
FRACTRAN命令 めいれい
State
State
条件 じょうけん アクション
次 つぎ
7
⋅
13
2
⋅
3
⋅
11
,
11
13
{\displaystyle {\frac {7\cdot 13}{2\cdot 3\cdot 11}},{\frac {11}{13}}}
A
v11, v13
v2 > 0 かつ
v2とv3からそれぞれ1を引 ひ 加 くわ
A
1
3
⋅
11
{\displaystyle {\frac {1}{3\cdot 11}}}
v2 = 0 かつ
v3から1を引 ひ
X
5
⋅
17
11
{\displaystyle {\frac {5\cdot 17}{11}}}
v3 = 0
v5に1を加 くわ
B
3
⋅
19
7
⋅
17
,
17
19
{\displaystyle {\frac {3\cdot 19}{7\cdot 17}},{\frac {17}{19}}}
B
v17, v19
v7 > 0
v7から1を引 ひ 加 くわ
B
11
17
{\displaystyle {\frac {11}{17}}}
v7 = 0
なし
A
1
3
{\displaystyle {\frac {1}{3}}}
X
v3 > 0
v3から1を引 ひ
X
v3 = 0
停止 ていし
FRACTRANプログラムに書 か 出 だ 以下 いか
(
91
66
,
11
13
,
1
33
,
85
11
,
57
119
,
17
19
,
11
17
,
1
3
)
{\displaystyle \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)}
入力 にゅうりょく n d 対 たい q r 出力 しゅつりょく n = qd + r かつ 0 ≤ r < d である。
コンウェイの素数 そすう 生成 せいせい 前述 ぜんじゅつ 本質 ほんしつ 的 てき ２ ふた 内 ない 商 しょう
2
n
7
m
{\displaystyle 2^{n}7^{m}}
m < n ）の形 かたち 与 あた 入力 にゅうりょく 対 たい n +1の最大 さいだい 約数 やくすう k を見 み n +1をn から1までの整数 せいすう 割 わ n +1k -1返 かえ 繰 く 返 かえ 生成 せいせい 番号 ばんごう 列 れつ 乗 じょう 生成 せいせい 指数 しすう 指数 しすう 素数 そすう 段階 だんかい 的 てき 説明 せつめい
このプログラムにおいて、素数 そすう 得 え 必要 ひつよう オンライン整数 せいすう 列 れつ 大 だい 辞典 じてん の数列 すうれつ A007547 ）
コンウェイのプログラムには前述 ぜんじゅつ 分数 ぶんすう 異 こと 版 はん 存在 そんざい [1]
(
17
91
,
78
85
,
19
51
,
23
38
,
29
33
,
77
29
,
95
23
,
77
19
,
1
17
,
11
13
,
13
11
,
15
14
,
15
2
,
55
1
)
{\displaystyle \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)}
方 ほう 少 すこ 速 はや 得 え 必要 ひつよう オンライン整数 せいすう 列 れつ 大 だい 辞典 じてん の数列 すうれつ A007546 ）このプログラムの特定 とくてい 整数 せいすう N が素数 そすう 調 しら 反復 はんぷく 以下 いか 数 かず 必要 ひつよう
N
−
1
+
(
6
N
+
2
)
(
N
−
b
)
+
2
∑
d
=
b
N
−
1
⌊
N
d
⌋
{\displaystyle N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor }
b
<
N
{\displaystyle b<N}
最大 さいだい N の整数 せいすう 約数 やくすう
⌊
x
⌋
{\displaystyle \lfloor x\rfloor }
床 ゆか 関数 かんすう [2]
以下 いか 年 ねん 少 すこ 短 みじか 命令 めいれい [3]
(
7
3
,
99
98
,
13
49
,
39
35
,
36
91
,
10
143
,
49
13
,
7
11
,
1
2
,
91
1
)
{\displaystyle \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)}
初期 しょき 値 ち n = 10において、連続 れんぞく 素数 そすう 後続 こうぞく 乗 じょう 生成 せいせい
以下 いか
(
3
⋅
11
2
2
⋅
5
,
5
11
,
13
2
⋅
5
,
1
5
,
2
3
,
2
⋅
5
7
,
7
2
)
{\displaystyle \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)}
(
20
33
,
5
11
,
13
10
,
1
5
,
2
3
,
10
7
,
7
2
)
{\displaystyle \left({\frac {20}{33}},{\frac {5}{11}},{\frac {13}{10}},{\frac {1}{5}},{\frac {2}{3}},{\frac {10}{7}},{\frac {7}{2}}\right)}
進 しん 記数 きすう 法 ほう a のハミング重 おも H(a )、すなわちa の2進数 しんすう 表記 ひょうき 1 の個数 こすう 計算 けいさん 入力 にゅうりょく a 出力 しゅつりょく H(a ) である。[4] 解析 かいせき 以下 いか
FRACTRAN命令 めいれい
State
State
条件 じょうけん アクション
次 つぎ
3
⋅
11
2
2
⋅
5
,
5
11
{\displaystyle {\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}}}
A
v5, v11
v2 > 1
v2から2を引 ひ 加 くわ
A
13
2
⋅
5
{\displaystyle {\frac {13}{2\cdot 5}}}
v2 = 1
v2から1を引 ひ 加 くわ
B
1
5
{\displaystyle {\frac {1}{5}}}
v2 = 0
なし
B
2
3
{\displaystyle {\frac {2}{3}}}
B
None
v3 > 0
v3から1を引 ひ 加 くわ
B
2
⋅
5
7
{\displaystyle {\frac {2\cdot 5}{7}}}
v3 = 0 かつ
v7から1を引 ひ 加 くわ
A
7
2
{\displaystyle {\frac {7}{2}}}
v3 = 0 かつ
v2から1を引 ひ 加 くわ
B
v2 = 0 かつ
停止 ていし
^ Gödel numbering ゲーデル数 すう は、慣例 かんれい 適用 てきよう 直接 ちょくせつ 負 まけ 整数 せいすう 浮動 ふどう 小数点 しょうすうてん 数 すう 文字 もじ 列 れつ 間接 かんせつ 的 てき 表 あらわ 直接的 ちょくせつてき 使用 しよう 提案 ていあん 拡張 かくちょう 機能 きのう FRACTRAN++ （Written in English） 及 およ Bag （Written in English） などがある。^ Esolang FRACTRAN page （Written in English） に類似 るいじ 乗算 じょうざん 器 き 説明 せつめい
