FRACTRAN - FRACTRAN

FRACTRAN je Turing-kompletní esoterický programovací jazyk vynalezl matematik John Conway. Program FRACTRAN je objednaný seznam pozitivní zlomky společně s počátečním kladným celým číslem n. Program se spouští aktualizací celého čísla n jak následuje:

pro první zlomek F v seznamu, pro který nf je celé číslo, nahraďte n podle nf
opakujte toto pravidlo, dokud žádný zlomek v seznamu nevyprodukuje celé číslo, když se vynásobí n, pak zastavte.

Conway 1987 dává následující vzorec pro prvočísla ve FRACTRANU:^{[poznámka 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}} přesně)}

Začínání s n= 2, tento program FRACTRAN generuje následující posloupnost celých čísel:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (sekvence A007542 v OEIS )

Po 2 obsahuje tato sekvence následující síly 2:

{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,, tečky}

(sekvence A034785 v OEIS )

což jsou hlavní síly 2.

Porozumění programu FRACTRAN

Program FRACTRAN lze považovat za typ programu zaregistrovat stroj kde jsou registry uloženy v hlavních exponentech v argumentu n.

Použitím Gödelovo číslování, kladné celé číslo n může kódovat libovolný počet libovolně velkých kladných celočíselných proměnných.^{[poznámka 2]} Hodnota každé proměnné je zakódována jako exponent prvočísla v Prvočíselný rozklad celého čísla. Například celé číslo

{displaystyle 60 = 2 ^ {2} jsou 3 ^ {1} jsou 5 ^ {1}}

představuje stav registru, ve kterém jedna proměnná (kterou budeme nazývat v2) obsahuje hodnotu 2 a dvě další proměnné (v3 a v5) obsahují hodnotu 1. Všechny ostatní proměnné mají hodnotu 0.

Program FRACTRAN je seřazený seznam pozitivních zlomků. Každá frakce představuje instrukci, která testuje jednu nebo více proměnných, představovaných jejími hlavními faktory jmenovatel. Například:

{displaystyle f_ {1} = {frac {21} {20}} = {frac {3 obrázky 7} {2 ^ {2} obrázky 5 ^ {1}}}}

testy v2 a v5. Li ${displaystyle v_ {2} geq 2}$ a ${displaystyle v_ {5} geq 1}$ , potom odečte 2 od v2 a 1 od v5 a přidá 1 k v3 a 1 k v7. Například:

{displaystyle 60cdot f_ {1} = 2 ^ {2} imes 3 ^ {1} imes 5 ^ {1} cdot {frac {3 imes 7} {2 ^ {2} imes 5 ^ {1}}} = 3 ^ {2} je 7 ^ {1}}

Vzhledem k tomu, že program FRACTRAN je pouze seznamem zlomků, jsou tyto pokyny pro testování a snižování přírůstků jedinými povolenými pokyny v jazyce FRACTRAN. Kromě toho platí následující omezení:

Pokaždé, když se provede instrukce, proměnné, které se testují, se také sníží.
Stejnou proměnnou nelze v jedné instrukci dekrementovat ani inkrementovat (jinak by zlomek představující tuto instrukci nebyl v její nejnižší termíny ). Proto každá instrukce FRACTRAN spotřebovává proměnné při jejich testování.
Není možné, aby instrukce FRACTRAN přímo testovala, pokud je proměnná 0 (Nepřímý test však lze implementovat vytvořením výchozí instrukce, která je umístěna za další instrukce, které testují konkrétní proměnnou.).

Vytváření jednoduchých programů

Přidání

Nejjednodušší program FRACTRAN je jedna instrukce jako např

{displaystyle left ({frac {3} {2}} ight)}

Tento program lze reprezentovat jako (velmi jednoduchý) algoritmus takto:

FRACTRAN Návod	Stav	Akce
${displaystyle {frac {3} {2}}}$	v2> 0	Odečtěte 1 od verze 2 Přidejte 1 do v3
	v2 = 0	Stop

Vzhledem k počátečnímu zadání formuláře ${displaystyle 2 ^ {a} 3 ^ {b}}$ , tento program vypočítá sekvenci ${displaystyle 2 ^ {a-1} 3 ^ {b + 1}}$ , ${displaystyle 2 ^ {a-2} 3 ^ {b + 2}}$ atd., až nakonec po ${displaystyle a}$ kroky, nezůstávají žádné faktory 2 a produkt s ${displaystyle {frac {3} {2}}}$ již neposkytuje celé číslo; stroj se poté zastaví s konečným výstupem ${displaystyle 3 ^ {a + b}}$ . Proto přidává dvě celá čísla dohromady.

Násobení

Můžeme vytvořit „multiplikátor“ „smyčkováním“ přes „sčítač“. K tomu je třeba zavést státy do našeho algoritmu. Tento algoritmus bude mít řadu ${displaystyle 2 ^ {a} 3 ^ {b}}$ a vyrábět ${displaystyle 5 ^ {ab}}$ :

Aktuální stav	Stav	Akce	Další stát
A	v7> 0	Odečtěte 1 od verze 7 Přidejte 1 do v3	A
	v7 = 0 a v2> 0	Odečtěte 1 od verze 2	B
	v7 = 0 a v2 = 0 a v3> 0	Odečtěte 1 od verze 3	A
	v7 = 0 a v2 = 0 a v3 = 0	Stop
B	v3> 0	Odečtěte 1 od verze 3 Přidejte 1 do v5 Přidejte 1 do v7	B
B	v3 = 0	Žádný	A

Stav B je smyčka, která přidává v3 na v5 a také přesouvá v3 na v7, a stav A je vnější kontrolní smyčka, která opakuje smyčku ve stavu B v2 krát. Stav A také obnoví hodnotu v3 z v7 po dokončení smyčky ve stavu B.

Můžeme implementovat stavy pomocí nových proměnných jako indikátorů stavu. Stavové indikátory pro stav B budou v11 a v13. Všimněte si, že vyžadujeme dva indikátory řízení stavu pro jednu smyčku; primární příznak (v11) a sekundární příznak (v13). Protože každý indikátor je spotřebován vždy, když je testován, potřebujeme sekundární indikátor, který říká „pokračovat v aktuálním stavu“; tento sekundární indikátor je v další instrukci přepnut zpět na primární indikátor a smyčka pokračuje.

Přidáním indikátorů stavu FRACTRAN a pokynů do tabulky algoritmu násobení máme:

FRACTRAN Návod	Aktuální stav	Stát Ukazatele	Stav	Akce	Další stát
${displaystyle {frac {3} {7}}}$	A	Žádný	v7> 0	Odečtěte 1 od verze 7 Přidejte 1 do v3	A
${displaystyle {frac {11} {2}}}$			v7 = 0 a v2> 0	Odečtěte 1 od verze 2	B
${displaystyle {frac {1} {3}}}$			v7 = 0 a v2 = 0 a v3> 0	Odečtěte 1 od verze 3	A
			v7 = 0 a v2 = 0 a v3 = 0	Stop
${displaystyle {frac {5cdot 7cdot 13} {3cdot 11}}, {frac {11} {13}}}$	B	v11, v13	v3> 0	Odečtěte 1 od verze 3 Přidejte 1 do v5 Přidejte 1 do v7	B
${displaystyle {frac {1} {11}}}$	B	v11, v13	v3 = 0	Žádný	A

Když vypíšeme instrukce FRACTRAN, musíme dát instrukce stavu A jako poslední, protože stav A nemá žádné indikátory stavu - je to výchozí stav, pokud nejsou nastaveny žádné indikátory stavu. Takže jako program FRACTRAN se multiplikátor stává:

{displaystyle left ({frac {455} {33}}, {frac {11} {13}}, {frac {1} {11}}, {frac {3} {7}}, {frac {11} { 2}}, {frac {1} {3}} ight)}

Se vstupem 2^A3^b tento program produkuje výstup 5^ab. ^{[Poznámka 3]}

Výše uvedený program FRACTRAN, který počítá 3krát 2 (takže jeho vstup je

{displaystyle 2 ^ {3} jsou 3 ^ {2} = 72}

a jeho výstup by měl být

{displaystyle 5 ^ {6}}

protože 3 krát 2 se rovná 6.

Odečítání a dělení

Podobným způsobem můžeme vytvořit FRACTRAN „odečítač“ a opakované odečítání nám umožní vytvořit algoritmus „kvocientu a zbytku“ následovně:

FRACTRAN Návod	Aktuální stav	Stát Ukazatele	Stav	Akce	Další stát
${displaystyle {frac {7cdot 13} {2cdot 3cdot 11}}, {frac {11} {13}}}$	A	v11, v13	v2> 0 a v3> 0	Odečtěte 1 od verze 2 Odečtěte 1 od verze 3 Přidejte 1 do v7	A
${displaystyle {frac {1} {3cdot 11}}}$			v2 = 0 a v3> 0	Odečtěte 1 od verze 3	X
${displaystyle {frac {5cdot 17} {11}}}$			v3 = 0	Přidejte 1 do v5	B
${displaystyle {frac {3cdot 19} {7cdot 17}}, {frac {17} {19}}}$	B	v17, v19	v7> 0	Odečtěte 1 od verze 7 Přidejte 1 do v3	B
${displaystyle {frac {11} {17}}}$	B	v17, v19	v7 = 0	Žádný	A
${displaystyle {frac {1} {3}}}$	X		v3> 0	Odečtěte 1 od verze 3	X
	X		v3 = 0	Stop

Při psaní programu FRACTRAN máme:

{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}} ight)}

a vstup 2ⁿ3^d11 produkuje výstup 5^q7^r kde n = qd + r a 0 ≤ r < d.

Conwayův primární algoritmus

Výše uvedený algoritmus generování prime společnosti Conway je v podstatě algoritmus kvocientu a zbytku ve dvou smyčkách. Vzhledem k zadání formuláře ${displaystyle 2 ^ {n} 7 ^ {m}}$ kde 0 ≤ m < nse algoritmus pokouší rozdělit n+1 u každého čísla od n dolů na 1, dokud nenajde největší číslo k to je dělitel n+1. Potom vrátí 2ⁿ⁺¹ 7^k-1 a opakuje se. Jediným okamžikem, kdy posloupnost čísel stavů generovaných algoritmem vytvoří sílu 2, je čas k je 1 (takže exponent 7 je 0), který nastane, pouze pokud je exponent 2 prvočíslo. Podrobné vysvětlení Conwayova algoritmu lze nalézt v Havil (2007).

Další příklady

Následující program FRACTRAN:

{displaystyle left ({frac {3cdot 11} {2 ^ {2} cdot 5}}, {frac {5} {11}}, {frac {13} {2cdot 5}}, {frac {1} {5} }, {frac {2} {3}}, {frac {2cdot 5} {7}}, {frac {7} {2}} ight)}

vypočítá Hammingova hmotnost H (A) binární expanze A tj. počet 1 s v binární expanzi A.^[1] Vzhledem k vstupu 2^A, jeho výstup je 13^{H (A)}. Program lze analyzovat následovně:

FRACTRAN Návod	Aktuální stav	Stát Ukazatele	Stav	Akce	Další stát
${displaystyle {frac {3cdot 11} {2 ^ {2} cdot 5}}, {frac {5} {11}}}$	A	v5, v11	v2> 1	Odečtěte 2 od verze 2 Přidejte 1 do v3	A
${displaystyle {frac {13} {2cdot 5}}}$			v2 = 1	Odečtěte 1 od verze 2 Přidejte 1 do verze 13	B
${displaystyle {frac {1} {5}}}$			v2 = 0	Žádný	B
${displaystyle {frac {2} {3}}}$	B	Žádný	v3> 0	Odečtěte 1 od verze 3 Přidejte 1 do v2	B
${displaystyle {frac {2cdot 5} {7}}}$			v3 = 0 a v7> 0	Odečtěte 1 od verze 7 Přidejte 1 do v2	A
${displaystyle {frac {7} {2}}}$			v3 = 0 a v7 = 0 a v2> 0	Odečtěte 1 od verze 2 přidat 1 do v7	B
			v2 = 0 a v3 = 0 a v7 = 0	Stop

Poznámky

^ v Kniha čísel, John Conway a Richard Guy dal trochu jinou sekvenci: ${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}} ight)}$
^ Gödelovo číslování nelze přímo použít pro záporná celá čísla, čísla s plovoucí desetinnou čárkou nebo textové řetězce, i když je možné přijmout konvence, které tyto datové typy představují nepřímo. Navrhovaná rozšíření FRACTRAN zahrnují FRACTRAN ++ a Taška.
^ Podobný multiplikační algoritmus je popsán na Stránka Esolang FRACTRAN.

Reference

^ John Baez, Puzzle # 4, The n-Category Café

Conway, John H. (1987). "FRACTRAN: Jednoduchý univerzální programovací jazyk pro aritmetiku". Otevřené problémy v komunikaci a výpočtu. Springer-Verlag New York, Inc .: 4–26. doi:10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6.CS1 maint: ref = harv (odkaz)
Conway, John H .; Guy, Richard K. (1996). Kniha čísel. Springer-Verlag New York, Inc. ISBN 0-387-97993-X.
Havil, Julian (2007). Bez přeplnění!. Princeton University Press. ISBN 0-691-12056-0.
Roberts, Siobhan (2015). "Kritéria ctnosti". Genius At Play - The Curious Mind of John Horton Conway. Bloomsbury. str. 115–119. ISBN 978-1-62040-593-2.

Viz také

Počítač s jednou instrukcí

externí odkazy

[1] v Kniha čísel, John Conway a Richard Guy dal trochu jinou sekvenci: ${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}} ight)}$

[2] Gödelovo číslování nelze přímo použít pro záporná celá čísla, čísla s plovoucí desetinnou čárkou nebo textové řetězce, i když je možné přijmout konvence, které tyto datové typy představují nepřímo. Navrhovaná rozšíření FRACTRAN zahrnují FRACTRAN ++ a Taška.

[3] Podobný multiplikační algoritmus je popsán na Stránka Esolang FRACTRAN.

[4] John Baez, Puzzle # 4, The n-Category Café

[poznámka 1]

[poznámka 2]

[Poznámka 3]

[1]