FRACTRAN

FRACTRAN er et Turing-komplet esoterisk programmeringssprog foreslået af John Conway .

Beskrivelse

Et FRACTRAN-program skrives som en ordnet liste over positive brøker sammen med et indledende positivt heltal input n . Programmet startes ved at opdatere hele tallet n som følger:

for den første fraktion på listen, som produktet er et heltal for, erstattes med $f$ $n\cdot f$ $n$ $n\cdot f$
gentag denne regel, indtil ingen af brøkerne på listen producerer et heltal, når de ganges med , stop derefter. $n$

For eksempel genererer følgende program primtal :

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

Startende med n = 2 genererer dette program følgende sekvens af heltal:

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

Efter 2 indeholder denne sekvens følgende potenser af 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,\,\dots

sekvens A034785 i OEIS

som er primmagter af 2.

Forståelse af FRACTRAN-programmet

FRACTRAN-programmet kan opfattes som en type Minsky-maskine , hvor registre er gemt i simple eksponenter i n -argumentet .

Ved at bruge Gödel-nummerering kan et positivt heltal n kode for et vilkårligt antal vilkårligt store positive heltalsvariable. Værdien af hver variabel kodes som en eksponent for et primtal i en simpel heltalsfaktorisering . For eksempel et heltal

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

repræsenterer tilstanden af et register, hvor en variabel (som vi vil kalde ) indeholder værdien 2, og to andre variable ( og ) indeholder værdien 1. Alle andre variable indeholder værdien 0. $v_{2}$ $v_{3}$ $v_{5}$

FRACTRAN-programmet er en ordnet liste over positive fraktioner. Hver brøk er en instruktion, der tester en eller flere variable repræsenteret af dens nævners primfaktorer . For eksempel:

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

kontrollerer to variable og . Hvis og , så udføres opgaverne , , . For eksempel: $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}\ gange 7^{1}

Da FRACTRAN-programmet kun er en liste over brøker, er disse test-tildelingsinstruktioner de eneste gyldige instruktioner på FRACTRAN-sproget. Derudover gælder følgende begrænsninger:

Hver gang en instruktion udføres, dekrementeres de variabler, der testes.
Den samme variabel kan ikke både dekrementeres og øges i den samme instruktion (ellers ville den brøkdel, der repræsenterer den instruktion, ikke være irreducerbar ).
FRACTRAN-instruktionen er ikke i stand til direkte at kontrollere, om en variabel er lig med 0. Der er dog en indirekte måde at gøre dette på ved at oprette en instruktion, der placeres efter andre instruktioner, der tester for en bestemt variabel.

FRACTRAN

Beskrivelse

Forståelse af FRACTRAN-programmet

Links