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:
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 rp come il registro rappresentato dal primo p. Nell'esempio si hanno due registri: , contenente il valore 3, e , 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:
Controlla che i registro abbia valore maggiore o uguale ad 1 e che il registro abbia valore maggiore o uguale a 2. In caso positivo il registro viene decrementato di una unità, viene decrementato di 2 unità, ed vengono entrambi incrementati di una unità. Nel caso di n = 72 si ha:
È 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:
Con il valore iniziale .
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]:
Note
- ^ (EN) Sequenza A007542, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
- ^ (EN) Sequenza A034785, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
Bibliografia
- (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.
Voci correlate
- Linguaggio di programmazione
- Linguaggio di programmazione esoterico
- John Conway
Altri progetti
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file su FRACTRAN
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)