Existe-t-il aujourd'hui des langues complètes non-Turing à usage général?

Les langages complets non Turing offrent un grand avantage par rapport aux langages complets Turing car ils sont beaucoup plus analysables et offrent ainsi des possibilités d'optimisation beaucoup plus larges. Pourtant, ils sont à peine utilisés et l'exhaustivité de Turing est en fait vendue comme une bonne fonctionnalité.

Existe-t-il aujourd'hui des langages traditionnels non complets de Turing destinés à la programmation à usage général?

programming-languages turing-completeness MaiaVictor
la source

Je pense que les deux choses que vous recherchez sont incompatibles. S'il n'est pas complet, il ne peut pas être utilisé à des fins arbitraires.

Bobson

@Dokkat J'ai rouvert la question et supprimé la discussion Meta des commentaires. Veuillez noter que si vous êtes en désaccord avec l'une des directives du site, la bonne façon de la contester est de publier une discussion Meta; pas simplement l'ignorer. De plus, pour les questions subjectives, la clé du succès est une recherche préalable et une définition rigoureuse. Plus vous effectuez de recherches, plus votre question devient spécifique (et répondable) et plus vous vous éloignez de l'espace notoire «non constructif».

yannis

Aussi, pourquoi considérez-vous que les "possibilités d'optimisation plus larges" sont un "grand avantage"? Cela ne veut pas dire que l'optimisation ne vaut pas la peine, mais je ne dirais certainement pas que l'optimisation inhérente d'une langue est un "grand avantage" étant donné la puissance des ordinateurs modernes.

Bobson

Coq peut être considéré comme assez «courant dominant» dans son domaine, les concurrents (HOL, Agda, ACL et autres) étant beaucoup moins visibles.

SK-logic

Peut-être que je ne comprends pas vraiment ce qu'est la complétude de turing, mais comment une langue peut-elle être à usage général et non complète de Turing? Je pensais que le sens d'être non-Turing complet, n'est pas en mesure d'effectuer une tâche de calcul, visant ainsi un but spécifique ..?

Aviv Cohn

Réponses:

Il n'y a pas aujourd'hui de langues complètes polyvalentes non Turing. Il existe cependant plusieurs langues spécifiques au domaine complet non Turing. ANSI SQL, les expressions régulières, les langages de données (HTML, CSS, JSON, etc.) et les expressions s sont quelques exemples notables.

Il n'y a pas vraiment d'avantage pour les langages complets non Turing polyvalents. L'aspect "beaucoup plus analysable", qui je suppose est un clin d'œil au théorème de Rice, s'applique mais cela n'a pas beaucoup de sens pour les langages qui ciblent plusieurs domaines d'application différents, d'autres exigences ont priorité. La flexibilité de l'exhaustivité de Turing est beaucoup plus importante que sa complexité. Les langages de programmation, comme tous les autres logiciels, sont tous des compromis.

En revanche, pour les langues spécifiques à un domaine, ce pourrait être l'inverse. Si vous ne construisez pas "une seule langue pour les gouverner tous", vous êtes libre d'implémenter uniquement les fonctionnalités qui ont du sens pour le but très spécifique de votre langue. Et le plus souvent, l'intégralité de Turing n'en fait pas partie.

yannis
la source

CSS3 est Turing-complet.

SK-logic

@ SK-logic CSS a du sens sans HTML, il peut être appliqué à tout type de XML et rien ne vous empêche de l'implémenter pour tout autre format avec une forme à peu près compatible (arbres avec nœuds nommés, ordre des frères, etc.). J'ai personnellement écrit des règles CSS pour un fichier SVG. C'est juste beaucoup plus commun pour HTML parce que HTML est beaucoup plus commun que les autres formats.

@Mike, c'est une analogie cassée. La sémantique CSS3 est étroitement liée à la sémantique du langage de présentation.

SK-logic

Notez que SQL avec fenêtrage et CTE (c'est-à-dire SQL: 2003) est également Turing-complete.

Jörg W Mittag

"Il n'y a pas aujourd'hui de langages complets polyvalents non Turing traditionnels." - C sans stockage externe n'est pas Turing-complete, mais il est très polyvalent et grand public. (Eh bien, je dirais personnellement que c'est un langage spécifique au domaine pour écrire des noyaux Unix, et qu'il n'est même pas particulièrement bon dans ce domaine, mais le monde n'est pas d'accord.)

Jörg W Mittag

-3

La raison pour laquelle les langues incomplètes de Turing ne sont pas courantes est qu'il est facile d'implémenter la vôtre chaque fois que vous en avez besoin et quelle que soit la façon dont vous en avez besoin. Un exemple intéressant est le script bitcoin: https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp

Adam Kurkiewicz
la source

Vraiment? Cela vous dérange d'implémenter Coq à partir de zéro, si c'est aussi simple que cela?

SK-logic

est-ce seulement votre avis ou vous pouvez le sauvegarder d'une manière ou d'une autre?

moucher

Les exemples sont tous les langages spécifiques au domaine qui n'ont pas besoin de récursivité, d'itérations illimitées ou d'autres tarpits de Turing. De plus, je suis sûr que la plupart d'entre nous ont mis en place une sorte de calculatrice simple traitant l'arithmétique de base.

MauganRa

Je suis d'accord cependant qu'il n'est pas trivial de garder le langage Turing-incomplet. Même sans tarpits de Turing évidents, il pourrait toujours contenir un bogue du compilateur qui permet d'utiliser l'une des plateformes sous-jacentes.

MauganRa