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:

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.

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.