Recentemente ho creato un linguaggio di programmazione esoterico e voglio sapere come testare e vedere se la lingua è Turing-Complete. La maggior parte dei posti che ho visto dicevano che aveva bisogno di cicli infiniti e di spazio di archiviazione infinito. È tutto?
Inoltre, ho bisogno di simulare una macchina di Turing per prove, o c'è un modo più semplice?
Si chiama NOR ed è molto diverso dalla maggior parte degli EPL che ho visto: NOR
No.
Posso provare che il linguaggio non è completo, perché posso risolvere il problema di interruzione. In effetti, posso farlo in due modi diversi, ognuno sfruttando aspetti diversi della tua lingua.
Innanzitutto, nessuno dei tuoi rami è condizionale. Nessuno dei valori calcolati influisce sul fatto che venga o meno effettuato un salto. Ciò significa che una volta inserito un ciclo, si è sempre in un ciclo infinito. Ogni volta che la stessa riga di codice viene eseguita due volte, so che il programma è in un ciclo infinito. Quindi posso dire se un programma si fermerà o meno osservando la sua esecuzione. Finirà (nel qual caso si ferma) o inizierà a ripetere le linee di esecuzione (nel qual caso non si fermerà mai).
In secondo luogo, la dimensione della memoria è fissa. Sì, puoi avere programmi più lunghi e quindi avere più memoria, ma una volta avviato il programma, la quantità di memoria è fissa. Ciò significa che per un programma con n di righe, so che ci sono solo 2^n*n di stati possibili per il programma. Ciò significa che se un programma non si ferma entro i primi step 2^n*n , deve trovarsi in uno stato precedentemente visitato e quindi in un ciclo infinito. Di conseguenza, posso testare l'arresto semplicemente osservando il programma per vedere se si ferma entro 2^n*n passi.
Ci sono molti modi di essere completi, ma per una lingua simile alla tua, hai bisogno di una memoria illimitata e di rami condizionali.
I recently made an esoteric programming language, and I want to know how to test and see if the language is Turing-Complete.
La tua lingua è " Turing-complete " se può simulare qualsiasi arbitrario stato singolo Turing machine . In alternativa, con la definizione di Turing-completezza, la tua lingua è anche Turing-completa se può simulare qualsiasi altra lingua o modello computazionale completa di Turing, come λ-calculus , funzioni μ-ricorsive , la lingua WHILE , la Calcolo combinatore SK (I) , un sistema di tag ciclici , Brainfuck , Regola 110 , Conway's Game of Life , java , , php , html5 + css3 , sql : 2003, ...
Most places I looked said it needed infinite loops and infinite data storage. Is that all?
Ci sono molti, molti modi in cui una lingua può essere completata da Turing. Un esempio sono le ramificazioni condizionali e la capacità di manipolare la memoria illimitata. (Questa è la funzione minima impostata per i linguaggi imperativi "normali" non patologici, non esoterici.)
Ma, per esempio, il calcolo λ non ha loop e non ha memoria dati; non ha nemmeno "dati". Ha solo due cose: l'astrazione della funzione e l'applicazione della funzione. Ciò nonostante è sufficiente per completare Turing.
Also, do I need to simulate a Turing Machine for proof, or is there an easier way?
Devi simulare, o dover dimostrare che puoi simulare, qualche lingua o sistema completo di Turing. Non deve essere necessariamente collegato a Turing Machines, deve essere solo completo di Turing.
Ad esempio, SQL ha dimostrato di essere Turing -completa implementando un sistema di tag ciclico , HTML5 + CSS3 ha dimostrato di essere completato da Turing implementando la regola 110 , Il sistema di tipo Scala ha dimostrato di essere Turing -completa implementando il calcolo del combinatore SKI .
Nota: è non abbastanza per simulare a Turing Machine. Devi o simulare qualsiasi macchina a nastro singolo o una Universal Turing Machine (che a sua volta può simula qualsiasi macchina di Turing a singolo nastro).
Leggi altre domande sui tag turing-completeness