Quali sono le linee guida pratiche per la valutazione della completezza di Turing di una lingua & # 8221 ;?

https://stackoverflow.com/questions/449014

19-08-2019
|

Domanda

Ho letto " what-is-turing-complete " e la Wikipedia pagina, ma sono meno interessato a una prova formale che alle implicazioni pratiche di essere Turing Complete.

Quello che sto effettivamente cercando di decidere è se il linguaggio del giocattolo che ho appena progettato potrebbe essere usato come linguaggio generico. So di poterlo provare se riesco a scrivere una macchina Turing con essa. Ma non voglio fare questo esercizio finché non sono abbastanza sicuro del successo.

Esiste un set minimo di funzionalità senza le quali Turing Completezza è impossibile? Esiste un insieme di funzionalità che garantisce praticamente completezza?

(La mia ipotesi è che la ramificazione condizionale e un archivio di memoria leggibile / scrivibile mi porteranno quasi ovunque)

EDIT:

Penso di essere andato su una tangente dicendo " Turing completo " ;. Sto cercando di indovinare con ragionevole sicurezza che un linguaggio appena inventato con un determinato set di funzionalità (o in alternativa, una VM con un determinato set di istruzioni) sarebbe in grado di calcolare qualsiasi cosa valga la pena di essere elaborata. So che provare che puoi costruire una macchina Turing con essa è un modo, ma non l'unico.

Quello che speravo fosse una serie di linee guida come: " se può fare X, Y e Z, può probabilmente fare qualsiasi cosa " ;.

Soluzione

Hai bisogno di qualche forma di costrutto di allocazione dinamica ( malloc o new o contro ) e funzioni ricorsive o qualche altro modo di scrivendo un ciclo infinito. Se li hai e riesci a fare qualcosa di interessante, sei quasi sicuramente Turing-completo.

Il calcolo lambda è equivalente in potenza a una macchina di Turing, e se si implementa il calcolo lambda è in realtà abbastanza divertente scrivere programmi di calcolo lambda. Way più divertente della scrittura di un programma per una macchina Turing!

L'unica implicazione pratica della completezza di Turing di cui sono a conoscenza è che puoi scrivere programmi che non terminano. Ho usato un paio di lingue speciali che garantiscono la risoluzione e quindi non Turing complete. A volte è utile rinunciare al potere espressivo extra in cambio di una risoluzione garantita.

Altri suggerimenti

"Turing Completeeness" descrive la proprietà di poter esprimere qualsiasi calcolo algoritmico, che era il punto di Turing's Machine in primo luogo. Un linguaggio o un sistema logico può essere descritto come "Turing completo" se ha questa proprietà. Da un punto di vista pratico tutti i linguaggi di programmazione per scopi generali - e un numero sorprendentemente elevato di linguaggi per scopi speciali - possono farlo per una definizione opportunamente sciolta (vedi sotto).

Tuttavia, una definizione rigorosa di completezza di Turing implica una capacità di archiviazione infinita, che ovviamente non è fisicamente possibile. Detto questo, nessuna macchina fisica può essere Turing Complete, ma questo vincolo è generalmente rilassato (almeno informalmente) quando si attribuisce Turing Completezza a un linguaggio di programmazione. Un banale test di completezza di Turing per una lingua è se la lingua può essere utilizzata per implementare un simulatore di Turing Machine.

Un esempio di un sistema diffuso che non è Turing Complete è Algebra relazionale, la base teorica dietro SQL come descritto nel documento di Codd Un modello relazionale per grandi banche dati condivise. Algebra relazionale ha la proprietà di completezza di Godel , il che significa che può esprimere qualsiasi calcolo che può essere definito in termini di calcolo predicato del primo ordine (ovvero espressioni logiche ordinarie). Tuttavia, non è Turing-Complete in quanto non può esprimere un calcolo algoritmico arbitrario.

Si noti che la maggior parte, se non tutti, i pratici dialetti SQL estendono il modello relazionale puro con costrutti procedurali nella misura in cui sono Turing completi dalla definizione normalmente applicata ai linguaggi di programmazione. Tuttavia, una singola query SQL in generale non lo è.

Alcuni esempi più eclatanti di lingue specifiche del dominio Turing Complete sono TeX e sendmail.cf, . In quest'ultimo caso c'è in realtà un famoso esempio di qualcuno che usa sendmail.cf per implementa un simulatore di Turing Machine universale.

Se riesci a scrivere un interprete Brainf $ & amp; # nella tua lingua, è Turing -completare. LOLCODE ha dimostrato di essere Turing completo esattamente in questo modo.

Esempi di lingue che non sono complete di Turing hanno spesso loop limitati , come:

for i=1 to N {...}

ma mancano di loop illimitati che controllano una condizione più generale, come:

while bool_expr {...}

Se tutti i possibili costrutti di loop sono limitati, il tuo programma è garantito per terminare. E, sebbene una garanzia di risoluzione incondizionata sia potenzialmente utile, è anche un'indicazione che la lingua non è completa di Turing.

Nota anche che inchiodare tutti i possibili costrutti di loop può essere difficile; ad esempio, sono abbastanza sicuro che i modelli C ++ non intendessero essere Turing-completi ...

Non sono sicuro che esista un "minimo set di funzionalità", ma per dimostrare che una lingua è Turing completa, devi solo provare che può emulare un altro sistema completo di Turing (non necessariamente una macchina Turing), fintanto che è noto che l'altro sistema è Turing completo. http://en.wikipedia.org/wiki/Turing_complete#Examples ha un intero elenco dei sistemi completi di Turing. Alcuni di loro sono più semplici delle macchine di Turing.

Vorrei aggiungere un avvertimento a ciò che Norman Ramsey ha detto: una macchina di Turing ha una memoria infinita e quindi i linguaggi di programmazione che sono considerati completi di Turing sono solo così supponendo che anche la memoria sia infinita.

Brainfuck è Turing completo e ha solo strutture ad anello e incremento / decremento della memoria, quindi questo è sufficiente.

D'altra parte non c'è modo di modificare alcun valore nel calcolo lambda, ma è Turing completo, quindi è chiaramente possibile farlo senza memoria mutabile.

Molto probabilmente il tuo programma non ha nulla a che fare con il calcolo lambda, quindi per una risposta pratica il minimo deve essere

Un modo per scrivere in una variabile
Un modo per leggere una variabile
Una forma di goto condizionale (if statement, while loop, ecc.)

Non ricordo di aver visto nulla di simile a funzioni minime per Turing Completezza. Tuttavia, se la tua lingua supporta loop e rami condizionali, le possibilità che sia Turing completa sono buone. Tuttavia, l'unico modo per dimostrarlo è ancora simulare una macchina Turing o un altro linguaggio Turing Complete.

Se puoi implementare una macchina di Turing (per quanto possono essere implementate, dato che sono costrutti matematici con memoria illimitata [la dimensione del nastro è infinte]) allora puoi essere sicuro che sia Turing completa.

Alcune indicazioni:

È possibile controllare la memoria e manipolarla in base al valore corrente e utilizzarla per controllare il flusso del programma.
Quella memoria può essere allocata memoria, stringhe che è possibile aggiungere, uno stack su cui è possibile allocare memoria attraverso la ricorsione ecc.
Il flusso del programma può avvenire tramite iterazione o ricorsione basata sulla selezione.

Qualsiasi lingua in grado di non terminare è praticamente Turing Complete. Puoi rendere un linguaggio non terminante capace dandogli strutture cicliche illimitate (come cicli While o un Goto che può raggiungere di nuovo), o dandogli una ricorsione generale (lasciando che una funzione si chiami da sola senza restrizioni.)

Una volta completato il turing, puoi fare cose come interpretare altre lingue Turing Complete, incluso il tuo.

La vera domanda è " a che serve? " Se la tua lingua verrà utilizzata in un dominio specifico per risolvere problemi specifici, potrebbe essere meglio trovare un modo per formulare le soluzioni in una lingua che non è Turing Complete e quindi garantire una risposta.

Puoi sempre aggiungere Turing Completezza scrivendo " Fai questo, quello o qualunque altra cosa; ma fallo con il risultato fornito da X " in qualsiasi altra lingua completa di Turing, dove X è fornito da una lingua completa non di Turing.

Naturalmente, se vuoi usare solo una lingua, probabilmente sarebbe meglio essere Turing Complete ...

Puoi provare a emulare un OISC (One Instruction-Set Computer). Se puoi emulare una delle istruzioni lì, quindi poiché quelle singole istruzioni possono essere utilizzate per comporre una macchina Turing Complete, allora hai dimostrato che anche la tua lingua deve essere Turing Complete.

Esiste un set minimo di funzionalità senza le quali Turing Completezza è impossibile? Esiste un insieme di funzionalità che garantisce praticamente completezza?

Sì, è necessario che il flusso di controllo sia subordinato ai dati: ciò che viene spesso espresso come if . Ad esempio un calcolatore tascabile + - * / non è completo di Turing, poiché non è possibile esprimere i condizionali.

Devi anche essere in grado di esprimere un salto indietro a un punto precedente del programma, in cima al quale potresti implementare un loop. Ad esempio BPF, che proibisce i salti all'indietro per garantire la chiusura del programma, non è completo anche Turing.

Hai bisogno di spazio di archiviazione che sia leggibile e scrivibile e arbitrariamente grande. Ad esempio, un linguaggio che ha solo due variabili a 32 bit è limitato in ciò che può calcolare. Sono disponibili molte opzioni per la struttura dell'archiviazione: memoria indirizzata da puntatori, matrici, pile, celle contro, strutture dati pure, ecc.

Inoltre puoi creare qualsiasi altro linguaggio di programmazione: potrebbe non essere facile o veloce, ma è sufficiente.

... rispetto alle implicazioni pratiche dell'essere Turing Complete.

Dubito che ci siano implicazioni pratiche nell'essere completo Turing.

Se guardi alcuni degli esempi di macchine complete di Turing, ad esempio l'originale Turing machine , vedrai che sono così lontani dall'essere utili per calcoli reali che il concetto deve essere solo di interesse teorico.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow