Dove si accetta che una lingua debba essere Turing completa per essere valida, è effettivamente possibile avere un linguaggio di programmazione 'utile' che non è completo di Turing?
Dovrei chiarire che si tratta in particolare di "programmazione" delle lingue nel senso tradizionale, e non di markup o linguaggi di query.
Coq , Agda , HOL e ACL2 sono linguaggi molto utili ed estremamente potenti, sebbene non siano completi di Turing.
Una caratteristica comune che li rende non-Turing-completi è il fatto che è sempre possibile provare la risoluzione. Una limitazione molto semplice è sufficiente: le chiamate ricorsive sono consentite solo su termini provabilmente strutturalmente più piccoli. Pertanto, mentre non è possibile implementare un interprete per una lingua completa di Turing o anche per il linguaggio stesso molte altre utili cose sono ancora possibili, come un compilatore C certificato .
Penso che il termine "mini-lingua" di Yegge si riferisca al fatto che spesso è utile usare un linguaggio per problemi specifici in cui la lingua non richiede la completezza del completamento per svolgere il compito, e questo va al cuore di come le lingue complete non turing possono essere utili. link
Wikipedia risponde molto bene, proprio in linea con quello che ha detto il mio istinto. Per prima cosa stavo pensando la matematica pura, poi mi sono ricordato di regexp, e Wikipedia elenca Epigram che credo sarebbe nella "pura matematica".
Non-Turing-complete languages
Many computational languages exist which are not Turing complete. One such example is the set of regular languages, most commonly regular expressions, which are generated by finite automata. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata and context-free grammars, which are commonly used to generate parse trees in an initial stage of program compiling. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions, or a series of mathematical formulae in a spreadsheet with no cycles.[citation needed] In total functional programming languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory, whereas Epigram uses dependent types.
Data languages
The notion of Turing-completeness does not apply to languages such as XML, JSON, YAML and S-expressions, because they are typically used to represent structured data, not describe computation. These are sometimes referred to as markup languages, or more properly as "data description languages".
Indica anche che le rappresentazioni della struttura dati non sono linguaggi, ma penso che l'XSLT debba essere considerato come una rappresentazione del calcolo, forse XPath non basato su ciò che Yannis ha detto in precedenza riguardo all'essere un linguaggio di query e non un linguaggio di calcolo. Forse T-SQL o PL / SQL contano come linguaggi computazionali anche se puoi fare una grande quantità di calcoli usando i loro aggregati, dove la forma generalizzata di SQL non specifica forse gli aggregati.
Capisco che SQL sia abbastanza popolare tra i tipi di business
La completezza di Turing è necessaria perché una lingua possa essere utilizzata come linguaggio generico. Ma non è sufficiente , cioè perché è completo di Turing, non è adatto per ogni dominio problematico:
Viceversa un DSL è adatto per il dominio del problema per il quale è stato progettato (supponendo che sia stato progettato in modo decente ), anche senza completezza di Turing:
* IIRC è stato dimostrato che HTML con animazioni CSS è completo di Turing, utilizzandole per implementare Conway's Game of Life su un array di checkbox. Ma l'utilità di HTML rimane valida anche nei browser che non supportano le animazioni CSS.
Esistono effettivamente linguaggi di programmazione, in cui è possibile scrivere solo programmi "efficienti". Efficiente in questo senso significa che ogni programma scritto in tale linguaggio rappresenta una lingua in P . Bellantoni, Niggl e Schwichtenberg descrivi una lingua del genere qui .
Il preprocessore C non è completo di Turing (in base alla progettazione), tuttavia può ancora implementare un interprete per una lingua che è Turing completo (Order-the-language, come descritto nella documentazione, è fondamentalmente solo una cosa tipo ML / Scheme puramente funzionale e sarebbe relativamente irrilevante - probabilmente abbastanza bello da usare - se non fosse per l'implementazione insolita).
Il trucco dietro di esso è simile agli argomenti sopra riportati sull'implementazione di una macchina di Turing in un universo fisico finito: il preprocessore C non può fornire un numero infinito di passi, o celle di dati, al lingua, ma può:
fornisce un numero dinamico irragionevolmente grande (2 ^ 64 o così di default), abbastanza grande per risolvere i problemi più realistici usando un processo di espansione esponenziale ( mumble mumble durata dell'universo mumble ).
usa un limite statico arbitrario per il numero precedente, cioè mentre il numero di passaggi deve essere un numero finito, puoi cambiare quello che il cap specifico è in "compile" -time di cambiare le impostazioni statiche del motore dell'interprete. Poiché non esiste un limite (teorico) sul valore effettivo di questo limite, esso può (teoricamente) essere esteso per soddisfare lo spazio richiesto per qualsiasi programma di chiusura.
Non argomentare che l'Ordine è necessariamente "utile" in sé, o che qualsiasi motore implementato da CPP sarebbe, ma è una prova di concetto interessante. È anche presumibilmente digitato dinamicamente , che è insolito per quest'area.
Sì, infatti è possibile avere una lingua utile che non è completa Turing. Vedi qui: link
Un altro esempio di un linguaggio Turing incompleto utile è SQL. (E ancora un altro è fogli di calcolo come Gnumeric o Excel, sebbene non siano realmente linguaggi di programmazione.)
Per quanto riguarda il motivo per cui si desidera un linguaggio che non sia Turing completo: perché ciò consente di ottenere alcune forti garanzie sul comportamento di runtime.
La completezza di Turing, in parole povere, significa avere una capacità di ricorsione. Avere ricorsione significa avere strutture potenzialmente illimitate in memoria. Dal momento che nel mondo reale la memoria non è infinita, la completezza di Turing richiede la gestione della memoria e / o la garbage collection.
La ricorsione del banning è un ottimo modo per evitare il problema veramente difficile della gestione delle risorse.
Nota bene! Essere Turing incompleto non implica necessariamente che qualsiasi programma terminerà necessariamente. Una lingua incompleta di Turing potrebbe consentire di valutare un elenco pigro infinito.
Un interessante "linguaggio di programmazione sub-Turing" non è stato menzionato fino ad ora quindi lo aggiungerò.
Si chiama "Crema" . Si descrive come:
Crema is a LLVM front-end that aims to specifically execute in sub-Turing Complete space. Designed to be simple to learn, and practical for the majority of programming tasks needed, Crema can restrict the computational complexity of the program to the minimum needed to improve security.
È piuttosto minimalista e piuttosto di basso livello.
Dovrebbe sembrare familiare agli sviluppatori C.
Inizialmente è stato finanziato dalla Defense Advanced Research Projects Agency (DARPA), ma al momento della stesura sembra abbastanza non mantenuto. Ma forse qualcuno è interessato comunque.
Leggi altre domande sui tag programming-languages turing-completeness language-features