Cosa rende un linguaggio Turing completo?

A Turing tarpit è una sorta di linguaggio di programmazione esoterico che si sforza di essere completo di Turing utilizzando il minor numero di elementi possibile. Brainfuck è forse il tarpit più noto, ma ce ne sono molti.

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

• OISC ( Un computer con set di istruzioni ) indica un tipo di calcolo imperativo che richiede solo unistruzione di uno o più argomenti, di solito “sottrarre e ramificare se minore o uguale a zero”, oppure “Sottrarre al contrario e saltare se prendere in prestito”. La MMU x86 implementa listruzione precedente ed è quindi completa di Turing.

In generale, per un linguaggio imperativo per essere completo di Turing, ha bisogno di:

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

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

Affinché un linguaggio funzionale basato su lambda-calculus sia TC, esigenze:

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

2. La capacità di applicare funzioni a argomenti (ad esempio, riduzione)

Ci sono ovviamente altri modi di guardare al calcolo, ma questi sono modelli comuni per i tarpits di Turing. Tieni presente che i computer reali non macchine di Turing universali perché non hanno memoria illimitata. A rigor di termini, sono “macchine di immagazzinamento delimitate”. Se continuassi ad aggiungere memoria a loro, si avvicinerebbero asintoticamente alle macchine di Turing al potere. Tuttavia, anche le macchine di memorizzazione limitate e le macchine a stati finiti sono utili per il calcolo; semplicemente non sono universali .

A rigor di termini, lI / O non è richiesto per la completezza di Turing; Il TC afferma solo che una lingua può calcolare la funzione che desideri, non che può mostrarti il risultato. In pratica, ogni linguaggio utile ha un modo per interagire in qualche modo con il mondo.

Commenti

• Per i linguaggi imperativi, sono sufficienti variabili semplici? Avevo limpressione che sarebbe stato necessario un qualche tipo di raccolta (ad esempio array o elenchi collegati).
• @luiscubal devi essere in grado di specificare una quantità arbitraria di dati. Con le variabili semplici puoi rappresentare la quantità di dati che le variabili stesse hanno. Cosa succede se è necessario rappresentare N + 1 diversi pezzi di dati. Si potrebbe obiettare che con trucchi come suona Fractran, potresti farlo anche con variabili semplici … ma che ‘ non è esattamente quello che ‘ stai chiedendo.
• Non è ‘ t ha richiesto che la lingua deve supportare ENDLESS loop?
• Re, ” ogni lingua utile ha un modo di interagire con il mondo. ” Algol 60 non aveva alcun modo definito di interagire con il mondo. Tutto il tuo I / O in un programma Algol 60 è stato eseguito chiamando le funzioni di libreria e le funzioni di libreria potrebbero essere completamente diverse in diverse implementazioni. Tuttavia, con la presente mi ritiro da qualsiasi discussione sul fatto che Algol 60 fosse ” utile. ”

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 Lo so), la tua lingua deve essere Turing-completa.Pertanto, se vuoi controllare se un linguaggio che hai progettato è completo di Turing, potresti semplicemente scrivere un Brainf *** al compilatore YourLanguage e dimostrare / dimostrare che può compilare tutti i programmi BF legali.

A 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).

Commenti

• Sì, questo sarebbe sicuramente il modo più pratico per affrontarlo. </sarcasm>
• @RobertHarvey ha ragione, ma lidea generale è abbastanza vitale. Brainfuck ha dimostrato di essere completo di turing e molto semplice come i linguaggi di programmazione. Per linguaggi di programmazione non esoterici, implementare un interprete brainfuck può essere molto più facile e veloce che dare una prova rigorosa dal nulla (posso implementare BF in un paio di righe di Python, ma io ‘ non sono sicuro di dove iniziare con una prova formale che Python è completo); e dozzine di linguaggi esoterici ispirati al brainfuck sono noti per essere completati perché ‘ sa come si mappano per brainfuck.
• @RobertHarvey: Perché no? Sicuramente qualcuno che progetta il proprio linguaggio sarebbe in grado di scrivere un compilatore BF (se fosse imperativo, e trovare un altro linguaggio adatto altrimenti).
• @delnan: Tu lo farai devi dimostrare, tuttavia, che il tuo interprete BF implementa correttamente la specifica BF, IOW dovrai dimostrare che il tuo interprete BF è, in effetti, un interprete BF e non un interprete per una lingua simile a BF che potrebbe o non potrebbe essere Turing-complete.
• @ DarekNędza, che ‘ è solo una conseguenza naturale di come viene definita la completezza di Turing; qualsiasi estensione di una lingua di Turing Complete sarà comunque Turing Complete.

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

Per verificare se qualcosa è completo di Turing, vedi se tu può 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) : abbastanza autoesplicativo.
2. La capacità di simulare lo spostamento della testina di lettura / scrittura : Non è sufficiente essere in grado di recuperare e memorizzare solo variabili. Deve anche essere possibile simulare la capacità di muovere la testina del nastro per fare riferimento ad altre variabili. Questo può spesso essere simulato allinterno dei linguaggi di programmazione con luso di strutture dati array (o equivalenti) o, nel caso di alcuni linguaggi come il codice macchina, la capacità di fare riferimento ad altre variabili attraverso luso di “puntatori” (o equivalenti).
3. La capacità di simulare una macchina a stati finiti : sebbene non menzionata spesso, le macchine di Turing sono in realtà una variazione delle macchine a stati finiti spesso utilizzate nello sviluppo dellIA. 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” arresto “: Sebbene sia spesso menzionato un insieme di regole deve essere in grado di ripetersi per poter essere considerato completo di Turing, questo non è davvero un buon criterio poiché la definizione formale di cosa un algoritmo è stato che gli algoritmi devono sempre concludere alla fine. Se non riescono a concludere in qualche modo, o non è completo di Turing, o detto algoritmo non è “una funzione calcolabile. Turing sistemi completi che tecnicamente non possono “concludere” a causa del modo in cui funzionano (come le console di gioco, per esempio) aggirare questa limitazione essendo in grado di “simulare” uno stato di arresto in qualche modo. Da non confondere con il “problema di arresto “, una funzione indecidibile che dimostra che è impossibile costruire un sistema in grado di rilevare con il 100% di affidabilità se un dato input fa sì che un altro sistema non concluda.

Questi sono il vero minimo requisiti per un sistema da considerare Turing completo. Niente di più, niente di meno. Se non può simulare nessuno di questi in qualche modo, non è Turing completo. I metodi proposti da altre persone sono solo mezzi fino alla fine poiché ci sono diversi sistemi completi di Turing che non hanno queste caratteristiche.

Nota che non esiste un modo noto per costruire effettivamente un vero sistema completo di Turing . Questo perché non esiste un modo noto per simulare veramente lillimitatezza del nastro della macchina di Turing nello spazio fisico.

Un linguaggio di programmazione diventa completo se puoi eseguire calcoli con esso.Non esiste un solo insieme di funzionalità che rende completo un turing linguistico, quindi le risposte che dicono che hai bisogno di cicli o che hai bisogno di variabili sono sbagliate poiché ci sono lingue che non ha nessuna delle due ma sono completi.

Alan Turing ha creato la macchina universale per la rotazione e se puoi tradurre qualsiasi programma progettato per funzionare sulla macchina universale per funzionare nella tua lingua, è anche Turing completo. Questo funziona anche indirettamente, quindi puoi dire che la lingua X è turing completa se tutti i programmi per turing complete la lingua Y possono essere tradotti per X poiché tutti i programmi della macchina turing universale possono essere tradotti in un programma Y.

La complessità temporale , complessità spaziale, formato di input / output semplice e facile da scrivere qualsiasi programma non sono inclusi nellequazione, quindi tale macchina può teoricamente fare tutti i calcoli se i calcoli non vengono interrotti dalla perdita di potenza o dalla Terra inghiottita dal sole.

Di solito per dimostrare la completezza del turing fanno un interprete per qualsiasi lingua che abbia dimostrato di essere turing completo, ma perché funzioni hai bisogno di mezzi di input e output, due cose che in realtà non sono richieste perché una lingua sia completa. È sufficiente che il tuo programma possa alterare il suo stato allavvio e che tu possa ispezionare la memoria dopo che il programma è stato interrotto.

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

Commenti

• ” Un linguaggio di programmazione è completo se puoi fare qualsiasi calcolo con esso. ” Questa ‘ è la tesi di Church-Turing, non ciò che rende un linguaggio Turing-completo.
• @Rhymoid Quindi intendi che nulla è completo se non puoi creare un interprete? Cioè. Lambda calcolo non è completo anche se ‘ è uguale a turing?
• Io ‘ sto ancora cercando una definizione autorevole dei termini Turing-equivalent e Turing-complete (e Turing-potente). I ‘ ho già visto troppi casi, da persone su bacheche di messaggi a ricercatori nei propri ‘ articoli, che interpretano questi termini in modo diverso.
• Comunque, Interpreto ‘ Turing-complete ‘ come una simulazione equivalente a una Universal Turing Machine (UTM; che, a sua volta, è in grado di simulare qualsiasi macchina di Turing, quindi ‘ universal ‘). Nellarticolo di Turing ‘ del 1936, dove presentò le sue macchine, definì la nozione di UTM e fornì uno schizzo di una prova che gli UTM sono simulazioni equivalenti a Church ‘ s lambda calcolo. In tal modo, ha dimostrato che avevano la stessa potenza di calcolo. La tesi di Church-Turing afferma, in parole povere, che ” che ‘ è tutta la potenza di calcolo che hai ‘ Avrai mai “.
• Ha due definizioni formali per Pagina di completezza di Turing di Wikipedia . Uno richiede I / O, laltro non ‘ t. Quella che ‘ non dice che una macchina sta tornando completa se può calcolare ogni funzione calcolabile da Turing. Ciò riporta il lambda calcolo al completamento del turing poiché puoi facilmente creare un programma uguale nel lambda calcolo che calcola lo stesso di qualsiasi programma di macchina turing.

Non puoi “dire se” verrà ripetuto allinfinito o si fermerà.

————-

Spiegazione: dato un input, è impossibile dire in ogni caso (usando unaltra macchina di Turing) se la cosa andrà in loop allinfinito o alla fine si fermerà, eccetto eseguendolo (che ti dà una risposta se lo fa stop, ma non se si ripete!).

Ciò significa che devi essere in grado di memorizzare una quantità potenzialmente illimitata di dati in qualche modo – ci deve essere un equivalente al nastro infinito, non importa come contorto! (Altrimenti ci sono solo un numero finito di stati e quindi puoi controllare se hai attraversato quello stato in precedenza e alla fine fermarti). In generale, le macchine di Turing possono aumentare o ridurre le dimensioni del loro stato con mezzi controllabili.

Poiché la macchina di Turing universale originale di Turing ha un problema di arresto irrisolvibile, anche la tua macchina completa di Turing deve avere un arresto 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 anche il tuo sistema è completo di Turing.

Per esempio, supponi di voler dimostrare che Snakes & Ladders è completo di Turing, data una tavola con una griglia ripetuta allinfinito (con una versione diversa in cima e lato sinistro). Sapendo che la macchina Minsky a 2 contatori è Turing completa (che ha 2 contatori illimitati e 1 stato su un numero finito), puoi costruire una scacchiera equivalente in cui 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 & Ladders Turing è completo.

Commenti

• Non ‘ t acquistare quellargomento. Solo perché il problema dellarresto è indecidibile per le macchine di Turing non implica direttamente che ogni notazione che consente di specificare un programma per il quale il problema dellarresto è indecidibile sia Turing completa. Ovviamente è vero solo il contrario: se la notazione è completa di Turing, allora è ovviamente possibile scrivere programmi per i quali il problema dellarresto è indecidibile.
• It ‘ una condizione necessaria. Se puoi decidere per ogni programma se si arresta, la lingua non è ‘ t Turing completa.

Una condizione necessaria è un ciclo con un numero massimo di iterazioni che non è determinato prima delliterazione, o una ricorsione in cui la profondità massima di ricorsione non è determinata prima. Ad esempio, i cicli for … in … come li trovi in molte lingue più recenti non sono sufficienti per completare il turing della lingua (ma avranno altri mezzi). Nota 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 di Ackermann non può essere calcolata in una lingua senza queste funzionalità. Daltra parte, è possibile scrivere un sacco di software altamente complesso e molto utile senza richiedere queste funzionalità.

Daltra parte, con ogni iterazione conta e ogni profondità di ricorsione calcolata in anticipo, non solo si può decidere se un programma si fermerà o meno, ma si si fermerà.

so che questa non è la risposta formalmente corretta, ma una volta che hai tolto il “minimo” da “Turing-complete” e hai rimesso “pratico” al suo posto, vedrai le caratteristiche più importanti che distinguono un linguaggio di programmazione da un linguaggio di markup sono

• variabili
• condizionali (if / then …)
• loopage (loop / break, while …)

prossimo com e

• Funzioni anonime e denominate

per testare queste asserzioni, inizia con un linguaggio di markup, ad esempio HTML. potremmo inventare un HTML + con solo variabili, o solo condizionali (MS lo ha fatto con commenti condizionali), o un qualche tipo di costrutto di ciclo (che in assenza di condizionali probabilmente finirebbe come qualcosa come <repeat n="4">...</repeat>). fare uno qualsiasi 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à, la rendi meno dichiarativa e più imperativa.

la ricerca della minimalità nella logica e nella programmazione è sicuramente importante e interessante, ma se dovessi insegnare a n00bies giovani o meno giovani “che cosè la programmazione” e “come imparare a programmare”, non avrei potuto iniziare con tutta lampiezza e lampiezza delle basi teoriche della completezza di Turing. lintera essenza della cucina e della programmazione è fare le cose, nel giusto ordine, ripetendo fino al momento, come ha fatto tua madre. questo riassume tutto per me.

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

Commenti

• Se non sei sicuro, dovresti prima cercarlo. fractran è turing complete , così come brainf * ck . Tieni presente inoltre che html 5 + CSS 3 è Turing completo perché può implementare regola 110 .
• yesyesyes lo so. ma tutti gli esempi forniti sono più o meno esoterici (anche se forse interessanti o sorprendenti), m La risposta è stata pragmatica, e molto probabilmente non minimale. Penso che ‘ sia importante sottolinearlo: questa pagina era la n. 1 durante la ricerca di Turing-completezza su Google, le risposte qui sono IMHO di scarsa utilità, ad esempio, per un n00bie chi vuole sapere cosa distingue HTML da PHP o Python. voglio dire, brainf ck non si chiama brainf ck senza motivo.