FRACTRAN

FRACTRAN è un linguaggio di programmazione esoterico Turing Completo inventato dal matematico John Conway.

Un programma FRACTRAN è formato da una lista di frazioni positive e un numero intero positivo, usato come valore in input n. Il programma viene eseguito aggiornando n secondo le regole:

1. partendo dalla prima frazione della lista, quando si incontra la prima frazione f tale che nf è intero, sostituisce n con il valore nf
2. si ripete finché nessuna frazione produce un intero se moltiplicato per n, quindi arresta.

Le regole posso anche essere viste come pseudo codice:

run = true
while run
   run = false
   for f in fractions 
      if f * n è intero
         run = true
         n = f * n
      end
   end
end

Nello pseudo codice mostrato sopra fractions è la lista delle frazioni fornita in ingresso e la variabile n contiene il valore iniziale fornito in input al programma. Il valore in output del programma, ossia il suo risultato, è il valore che assume la variabile intera n alla fine del programma.

Per ogni numero intero n è possibile definire la sua scomposizione in fattori primi. Ad esempio:

${\displaystyle 72=2^{3}\times 3^{2}.}$

FRACTRAN può essere visto come una macchina a registri in cui ogni fattore di n rappresenta un differente registro ed il suo esponente indica il valore immagazzinato all'interno del registro. Per comodità si definisce il registro r_p come il registro rappresentato dal primo p. Nell'esempio si hanno due registri: ${\displaystyle r_{2}}$, contenente il valore 3, e ${\displaystyle r_{3}}$, contenente il valore 2. Ogni altro registro assume automaticamente il valore 0.

Un programma FRACTRAN è una lista di frazioni. Ogni frazione del programma è un'istruzione condizionale di maggiore o uguale che opera sua alcuni registri, ossia quelli indicati nella fattorizzazione del denominatore, ed in caso positivo procede a decrementare i registri legati ai fattori del denominatore ed incrementare i registri legati ai fattori nel numeratore di f. Si noti che se almeno uno dei registri nel denominatore ha un valore maggiore di uno dei registri nella variabile n il prodotto nf non risulta intero e quindi viola la condizione dell'aggiornamento della variabile.

Ad esempio la frazione:

${\displaystyle f={\frac {35}{18}}={\frac {5\times 7}{2\times 3^{2}}}}$

Controlla che i registro ${\displaystyle r_{2}}$ abbia valore maggiore o uguale ad 1 e che il registro ${\displaystyle r_{3}}$ abbia valore maggiore o uguale a 2. In caso positivo il registro ${\displaystyle r_{2}}$ viene decrementato di una unità, ${\displaystyle r_{3}}$ viene decrementato di 2 unità, ${\displaystyle r_{5}}$ ed ${\displaystyle r_{7}}$ vengono entrambi incrementati di una unità. Nel caso di n = 72 si ha:

${\displaystyle n\times f=72\times {\frac {35}{18}}=2^{3}\times 3^{2}\times {\frac {5\times 7}{2\times 3^{2}}}=2^{2}\times 5\times 7=140}$

È interessante notare che:

• Ogni volta che una variabile supera un controllo essa è automaticamente decrementata
• Non è possibile testare ed incrementare una variabile in una sola istruzione. In tal caso la frazione non sarebbe ridotta ai minimi termini e le componenti del numeratore e del denominatore andrebbero a compensarsi.
• Non è possibile controllare direttamente se una variabile abbia valore 0 Tuttavia è possibile effettuare un controllo indiretto inserendo una condizione di default in fondo alla lista.

Conway, 1987 mostra come esempio il seguente programma per calcolare i numeri primi:

${\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)}$

Con il valore iniziale ${\displaystyle n=2}$.

Il programma genera la successione di numeri^[1]:

• 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...

Questa sequenza contiene, oltre a 2 le potenze prime di due^[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,\,\dots }$

• (EN) John H. Conway, FRACTRAN: A simple universal programming language for arithmetic, in Open Problems in Communication and Computation, Springer-Verlag New York, Inc., 1987, pp. 4–26, DOI:10.1007/978-1-4612-4808-8_2, ISBN 978-1-4612-9162-6.

• Linguaggio di programmazione
• Linguaggio di programmazione esoterico
• John Conway

• Wikimedia Commons contiene immagini o altri file su FRACTRAN

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica