FRACTRAN

FRACTRAN je Turingův kompletní esoterický programovací jazyk navržený Johnem Conwayem .

Popis

Program FRACTRAN je napsán jako uspořádaný seznam kladných zlomků spolu s počátečním kladným celým číslem n . Program se spustí aktualizací celého čísla n takto:

pro první zlomek v seznamu, pro který je součin celé číslo, nahraďte výrazem $F$ $n\cdot f$ $n$ $n\cdot f$
opakujte toto pravidlo, dokud žádný ze zlomků v seznamu nevytvoří po vynásobení číslem celé číslo , pak zastavte. $n$

Například následující program generuje prvočísla :

\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)

Počínaje n = 2 tento program generuje následující posloupnost celých čísel:

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

Po 2 tato sekvence obsahuje následující mocniny 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,\,\tečky

sekvence A034785 v OEIS

což jsou hlavní mocniny 2.

Pochopení programu FRACTRAN

Program FRACTRAN lze považovat za typ Minského stroje , kde jsou registry uloženy v jednoduchých exponentech v argumentu n .

Pomocí Gödelova číslování může kladné celé číslo n zakódovat libovolný počet libovolně velkých kladných celočíselných proměnných. Hodnota každé proměnné je zakódována jako exponent prvočísla v jednoduché celočíselné faktorizaci . Například celé číslo

60=2^{2}\times 3^{1}\times 5^{1}

představuje stav registru, ve kterém jedna proměnná (kterou budeme nazývat ) obsahuje hodnotu 2 a dvě další proměnné ( a ) obsahují hodnotu 1. Všechny ostatní proměnné obsahují hodnotu 0. $v_{2}$ $v_{3}$ $v_{5}$

Program FRACTRAN je uspořádaný seznam kladných zlomků. Každý zlomek je instrukce, která testuje jednu nebo více proměnných reprezentovaných prvočísly svého jmenovatele . Například:

{\displaystyle f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1))))

kontroluje dvě proměnné a . Jestliže a , pak se provedou přiřazení , , , . Například: $v_{2}$ $v_{5}$ $v_{2}\geq 2$ $v_{5}\geq 1$ $v_{2}:=v_{2}-2$ $v_{5}:=v_{5}-1$ $v_{3}:=v_{3}+1$ $v_{7}:=v_{7}+1$

60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5 ^{1}}=3^{2}\krát 7^{1}

Protože program FRACTRAN je pouze seznam zlomků, jsou tyto instrukce přiřazení testu jedinými platnými instrukcemi v jazyce FRACTRAN. Kromě toho platí následující omezení:

Pokaždé, když je instrukce provedena, jsou testované proměnné také dekrementovány.
Stejná proměnná nemůže být současně dekrementována a inkrementována ve stejné instrukci (jinak by zlomek reprezentující tuto instrukci nebyl neredukovatelný ).
Instrukce FRACTRAN není schopna přímo zkontrolovat, zda je proměnná rovna 0. Existuje však nepřímý způsob, jak toho dosáhnout vytvořením instrukce, která je umístěna za jinými instrukcemi, které testují určitou proměnnou.

Odkazy

"Patologie prvočísel: Fractran"
Weisstein, Eric W. "FRACTRAN". matematický svět.
Patologie prvočísel
FRACTRAN
Ruby implementace a ukázkové programy
Projekt Eulerův problém 308
„Budování Fizzbuzz ve Fractranu zdola nahoru“
Chris Lomont, „Univerzální tlumočník FRACTRAN ve FRACTRAN“