FRACTRAN
# FRACTRAN

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

## Struttura e Funzionamento di un programma FRACTRAN

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:

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

Le regole posso anche essere viste come pseudo codice:

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.

### Gestione delle Variabili

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

    $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: $r_{2}$, contenente il valore 3, e $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:

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

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

    $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.

### Un esempio

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

    $\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 $n=2$.

Il programma genera la successione di numeri:

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

Questa sequenza contiene, oltre a 2 le potenze prime di due:

    $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$
