Che cosa rende Turing una lingua completa?

Un taring di Turing è una sorta di linguaggio di programmazione esoterico che si sforza di essere completo di Turing mentre usa pochi elementi come possibile. Brainfuck è forse il tarpit più conosciuto, ma ce ne sono molti.

• Iota e Jot sono linguaggi funzionali con due e tre simboli, rispettivamente, basati sul calcolo combinatore SK (I) .

• OISC ( One Instruction Set Computer ) denota un tipo di calcolo imperativo che richiede solo un'istruzione di uno o più argomenti, in genere" sottrazione e diramazione se minore o uguale a zero "o" reverse sottrarre e saltare se si prende in prestito " ”. La MMU x86 implementa la precedente istruzione ed è quindi completa per Turing.

In generale, affinché un linguaggio imperativo sia completo di Turing, è necessario:

1. Una forma di ripetizione condizionale o salto condizionato (ad es., while , if + goto )

2. Un modo per leggere e scrivere una forma di archiviazione (ad es., variabili, nastro)

Per un linguaggio funzionale basato su lambda-calculus per essere TC, ha bisogno di:

1. La capacità di astrarre le funzioni su argomenti (ad es., astrazione lambda, citazione)

2. La capacità di applicare funzioni agli argomenti (ad es. riduzione)

Ci sono naturalmente altri modi di guardare al calcolo, ma questi sono modelli comuni per i tarpiti di Turing. Tieni presente che i computer reali sono non macchine di Turing universali perché non dispongono di spazio di archiviazione illimitato. A rigor di termini, sono "macchine per lo stoccaggio delimitate". Se si dovesse continuare ad aggiungere memoria, si avvicinerebbero asintoticamente alle macchine di Turing al potere. Tuttavia, anche le macchine di archiviazione limitate e le macchine a stati finiti sono utili per il calcolo; semplicemente non sono universal .

In senso stretto, I / O non è richiesto per la completezza di Turing; TC afferma solo che una lingua può calcolare la funzione desiderata, non che può mostrare il risultato. In pratica, ogni linguaggio utile ha un modo di interagire con il mondo in qualche modo.

Da un punto di vista più pratico: se puoi tradurre tutti i programmi in una lingua completa di Turing nella tua lingua, allora (per quanto ne so), la tua lingua deve essere completa per Turing. Pertanto, se vuoi verificare se una lingua che hai progettato è completa con Turing, puoi semplicemente scrivere un Brain *** nel tuo compilatore Your Language e dimostrare / dimostrare che può compilare tutti i programmi legali di BF.

Per chiarire, voglio dire che oltre a un interprete per YourLanguage, scrivi un compilatore (in qualsiasi lingua) che può compilare qualsiasi programma BF in YourLanguage (mantenendo la stessa semantica, ovviamente).

Un sistema può essere considerato come Turing completo solo se può fare qualsiasi cosa possa fare una macchina di Turing universale. Poiché la macchina di Turing universale si dice che sia in grado di risolvere qualsiasi funzione calcolabile, i sistemi completi di Turing possono, per estensione, anche farlo.

Per verificare se qualcosa è completato da Turing, vedi se è possibile implementare una macchina di Turing al suo interno. In altre parole, controlla se può simulare quanto segue:

1. La capacità di leggere e scrivere "variabili" (o dati arbitrari) : praticamente auto esplicativo.
2. La possibilità di simulare lo spostamento della testina di lettura / scrittura : non è sufficiente essere solo in grado di recuperare e memorizzare le variabili. Deve anche essere possibile simulare la capacità di spostare la testina del nastro per fare riferimento ad altre variabili. Questo può essere spesso simulato all'interno di linguaggi di programmazione con l'utilizzo di strutture di dati di array (o equivalenti) o, nel caso di alcuni linguaggi come il codice macchina, la possibilità di fare riferimento ad altre variabili attraverso l'uso di "puntatori" (o equivalenti).
3. La possibilità di simulare una macchina a stati finiti : sebbene non menzionata spesso, le macchine di Turing sono in realtà una variante delle macchine a stati finiti spesso utilizzate nello sviluppo di intelligenza artificiale. Alan Turing ha detto che lo scopo degli stati è quello di simulare le "varie modalità di risoluzione dei problemi" di una persona.
4. Uno stato di "interruzione" : sebbene venga spesso menzionato un insieme di regole deve essere in grado di ripetersi per contare come Turing completo, non è davvero un buon criterio in quanto la definizione formale di cosa un algoritmo è che gli algoritmi di stato devono sempre alla fine concludere. Se non riescono a concludere in qualche modo, o non è completo Turing, o detto algoritmo non è una funzione calcolabile. I sistemi completi di Turing che tecnicamente non riescono a concludere a causa del loro modo di lavorare (come le console di gioco, per esempio) aggirano questa limitazione essendo in grado di "simulare" uno stato di arresto in qualche modo. Da non confondere con il "problema dell'arresto", una funzione indecidibile che dimostra che è impossibile costruire un sistema in grado di rilevare con il 100% di affidabilità se un dato input causerà la mancata conclusione di un altro sistema.

Questi sono i veri requisiti minimi per un sistema da considerare Turing completo. Niente di più, niente di meno. Se non è in grado di simulare nessuno di questi in qualche modo, non è completo Turing. I metodi che altre persone propongono sono solo mezzi alla fine poiché esistono diversi sistemi completi di Turing che non hanno queste caratteristiche.

Si noti che non esiste un modo noto per costruire realmente un vero sistema completo di Turing. Questo perché non esiste un modo conosciuto per simulare sinceramente l'illimitatezza del nastro della macchina di Turing all'interno dello spazio fisico.

Un linguaggio di programmazione è completo se puoi fare qualsiasi calcolo con esso. Non c'è solo un set di funzionalità che rende completa la lingua, quindi le risposte che dicono che hai bisogno di loop o che hai bisogno di variabili sono sbagliate dato che ci sono lingue che non ha né ma sono completi.

Alan Turing ha creato la macchina universale e se è possibile tradurre qualsiasi programma progettato per funzionare sulla macchina universale da eseguire nella propria lingua, è anche completo. Questo funziona anche indirettamente, quindi puoi dire che il linguaggio X è completo se tutti i programmi per la traduzione completa della lingua Y possono essere tradotti per X poiché tutti i programmi di macchina universale possono essere tradotti in un programma Y.

La complessità temporale, la complessità dello spazio, il facile formato di input / output e la facilità di scrittura di qualsiasi programma non sono inclusi nell'equazione, quindi tale macchina può teoricamente fare tutti i calcoli se i calcoli non vengono fermati dalla perdita di potenza o dalla Terra ingerita da il sole.

Di solito per dimostrare la completezza di turing fanno un interprete per qualsiasi comprovato linguaggio completo, ma per far funzionare servono i mezzi di input e output, due cose che non sono realmente necessarie per completare una lingua. È sufficiente che il tuo programma possa alterarne lo stato all'avvio e che tu possa ispezionare la memoria dopo che il programma è stato fermato.

Per realizzare un linguaggio di successo, però, ha bisogno di qualcosa di più della completezza del tour, e questo è vero anche per i tarpit. Non credo che BrainFuck sarebbe stato popolare senza , e . .

Non puoi sapere se looperà all'infinito o si fermerà.

-------------

Spiegazione: dati alcuni input, è impossibile dire in ogni caso (usando un'altra macchina di Turing) se la cosa andrà in loop infinitamente o finirà per fermarsi, eccetto eseguendola (che ti dà una risposta se si ferma , ma non se loops!).

Ciò significa che devi essere in grado di memorizzare un numero potenzialmente illimitato di dati in qualche modo - ci deve essere un equivalente al nastro infinito, non importa quanto contorto! (Altrimenti c'è solo un numero finito di stati e quindi puoi controllare se hai già passato questo stato e alla fine fermarti). Generalmente, le macchine di Turing possono aumentare o ridurre le dimensioni del loro stato con alcuni mezzi controllabili.

Poiché la macchina di Turing universale originale di Turing ha un problema di interruzione irrisolvibile, anche la tua macchina completa di Turing deve avere un problema di interruzione irrisolvibile.

I sistemi completi di Turing possono emulare qualsiasi altro sistema completo di Turing, quindi se puoi costruire un emulatore per un sistema completo di Turing ben noto nel tuo sistema, ciò dimostra che il tuo sistema è anche completo di Turing.

Ad esempio, supponi di voler provare che Snakes & Le scale sono complete di Turing, dato un tabellone con una griglia ripetuta all'infinito (con una versione diversa nella parte superiore e sinistra). Sapendo che la macchina Minsky a 2 contatori è completa di Turing (che ha 2 contatori illimitati e 1 stato di un numero finito), puoi costruire una tavola equivalente dove la posizione X e Y sulla griglia è il valore corrente dei 2 contatori e il percorso corrente è lo stato corrente. Scoppio! Hai appena dimostrato che Snakes & Le scale sono complete di Turing.

Una condizione necessaria è un ciclo con un numero massimo di iterazioni che non viene determinato prima dell'iterazione o ricorsione in cui la massima profondità di ricorsione non viene determinata in anticipo. Ad esempio, per ... in ... i loop come li trovi in molte lingue più recenti sono non sufficienti a rendere completa la lingua (ma avranno altri mezzi). Si noti che questo non significa un numero limitato di iterazioni o una profondità di ricorsione limitata, ma che le iterazioni massime e la profondità di ricorsione devono essere calcolate in anticipo.

Ad esempio, la funzione Ackermann non può essere calcolata in una lingua senza queste caratteristiche. D'altra parte, un software molto complesso e molto utile può essere scritto senza richiedere queste funzionalità.

D'altro canto, ad ogni conteggio delle iterazioni e ad ogni profondità di ricorsione calcolata in anticipo, non solo si può decidere se un programma si fermerà o meno, ma si fermerà per .

so che questa non è la risposta formalmente corretta, ma una volta che prendi il "minimo" di "Turing-complete" e rimetti il "pratico" indietro a cui appartiene, vedrai le caratteristiche più importanti che distinguono una programmazione la lingua da un linguaggio di marcatura è

• variabili
• condizionali (se / allora ...)
• loopage (loop / break, while ...)

next come

• funzioni anonime e denominate

per testare queste asserzioni, iniziare con un linguaggio di marcatura, ad esempio HTML. potremmo inventare un HTML + solo con le variabili, o solo condizionali (MS lo ha fatto con i commenti condizionali), o qualche tipo di costrutto di loop (che in assenza di condizionali probabilmente finirà con qualcosa come <repeat n='4'>...</repeat> ). fare uno di questi renderà HTML + significativamente (?) più potente del semplice HTML, ma sarebbe comunque più un markup che un linguaggio di programmazione; con ogni nuova funzionalità, lo rendi meno di un linguaggio dichiarativo e più imperativo.

la ricerca della minimalità nella logica e nella programmazione è sicuramente importante e interessante, ma se dovessi insegnare ai giovani o ai vecchi "che cos'è la programmazione" e "come imparare a programmare", inizierei appena con il pieno ampiezza e larghezza dei fondamenti teorici della completezza di Turing. l'intera essenza della cucina e della programmazione sta facendo le cose, nell'ordine giusto, ripetendo fino al momento, come ha fatto tua madre. quello su riassume per me.

poi di nuovo, non ho mai finito il mio CS.