Ho cercato di google per la spiegazione, ma la maggior parte dei link dice solo cose come "FRACTRAN è completo." Ad esempio, diamo un'occhiata alla moltiplicazione. "
Ricordo di aver visto un post sul forum xkcd dire che FRACTRAN ha aiutato il poster a comprendere la completezza di Turing. Sto cercando una spiegazione intuitiva del perché questo esolang sia completo di Turing, in quanto non è molto ovvio osservare la meccanica della lingua.
Perché una lingua imperativa sia completa Turing deve avere:
FRACTRAN è un linguaggio composto da una serie di frazioni che memorizzano i suoi dati negli esponenti dei primi.
Diciamo che vuoi aggiungere due numeri: 2 a 3 b diventa 5 ab
455 11 1 3 11 1 --- , -- , -- , - , -- , - 33 13 11 7 2 3
Questo è un programma FRACTRAN per fare questo al di sopra del cambiamento.
Si inizia con un numero come 72 (2 3 3 2 ). Il programma va 'avanti' fino a trovare un numero che quando moltiplicato per l'istruzione è un altro numero intero (non sono ammessi remainder).
72 verrà eseguito fino a quando non arriva a 11/2 . Quindi dividerà il numero di 2 e lo moltiplicherà per 11 (la potenza in 11 è una variabile). Questo dà 396 . 396 è divisibile per 33 (riducendo la 3 potenza e la 11) e moltiplicato per 455 (incrementando 5, 7 e 13 variabili). E così via. La descrizione completa di questo programma e della sua tabella di stato può essere letta nella FRACTRAN pagina di Wikipedia, inclusa una bella gif animata del sopra il programma.
Altro materiale FRACTRAN su Stack Exchange che tocca la completezza di Turing può essere trovato all'indirizzo: Convertire Fractran in Brainfuck (ok, questo è un veramente uso produttivo del proprio tempo)
The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers.
Parte del trucco qui (e questo inizia a discostarsi dalla teoria) è che dietro le quinte, questo è un Minsky register machine per cui è stato provato che alcuni nastri (programmi) sono macchine di Turing IF il nastro è rappresentato come Numero Gödel che è esattamente quello che è il numero FRACTRAN (dalla pagina wikipedia collegata):
Gödel used a system based on prime factorization. He first assigned a unique natural number to each basic symbol in the formal language of arithmetic with which he was dealing.
Quindi abbiamo loop condizionali, variabili arbitrarie memorizzate come numeri di Gödel, abbiamo una macchina di Turing.
È possibile leggere altre divertenti letture che riguardano la natura di Collat come FRACTRAN all'indirizzo Non è possibile decidere? Undecide! che mette in relazione la congettura di Collatz con FRACTRAN e il problema dell'arresto.
FRACTRAN è un po 'difficile da capire.
Considera il programma qualcosa come:
LABEL: start
block1
block2
block3
...
END
In questo, ogni blocco ha il formato:
IF(registers X >= a, Y >= b) # or any combination of registers
THEN
X -= a
Y -= b
I += n
J += m
goto start
La prima affermazione del programma di moltiplicazione sopra:
455 --- 33
Verrebbe scritto in questo modulo come:
IF(register '3' >= 1 && '11' >= 1)
THEN
'3' -= 1
'11' -= 1
'5' += 1
'7' += 1
'13' += 1
goto start
E così puoi vedere chiaramente la memoria dei dati e i costrutti di loop necessari per la completezza di Turing. È molto rudimentale, ma esiste e funziona come una semplice macchina di registro, ma questo è tutto ciò che è veramente necessario essere in grado di fare.
Non sei ancora convinto?
Questo in gran parte prende in prestito da una conferenza di Dimitri Hendricks su Modelli di calcolo
Questo prende il semplicissimo programma (2/3) che è un sommatore (2 a 3 b - > 3 a + b ) Ma è distruttivo: il valore in 2 viene cancellato come parte del processo.
Consente di scrivere un FRACTRAN di livello superiore che rende facile non effettuare tale distruzione.
Il programma originale potrebbe essere pensato come:
2 α: - → α 3
In F 2 , si possono specificare "funzioni" di un ordinamento.
10 1
α: -- → α , - → β
3 1
3
β: - → β
5
Per convertire un programma F 2 (P) in un programma FRACTRAN standard, uno fa:
a c e p: - → q, - → r, - -> s, ... b d f
diventa:
aq cr es -- , -- , -- , ... bp dp fp
Ciò che è stato fatto è usare i primi p, q, r e s per memorizzare lo stato del programma.
E poi abbiamo la macchina del registro ... ha un numero finito di registri che memorizzano numeri grandi e arbitrari e due istruzioni:
Questa macchina di registro ha dimostrato di essere completa Turing.
Quindi va a mostrare il processo su più diapositive di compilazione di un programma macchina di registro in un programma FRACTRAN come parte di un processo meccanico.
In sostanza:
p(i)
inc(x(i), m) = ---- → m
1
1 1
jzdec(x(i), m1, m2) = ---- → m2, - → m1
p(i) 1
E quindi a causa dell'equivalenza tra questi due modelli di calcolo, FRACTRAN è completo di Turing.
A proposito, se vuoi davvero avere la mente gonfia, leggi Code Golf: Fractran in cui alcune persone hanno scritto un programma FRACTRAN per eseguire un altro programma FRACTRAN.
Leggi altre domande sui tag turing-completeness