Quels sont les critères ou les fonctionnalités de base requises pour indiquer que x ou y est (ou n'est pas ) Un langage de programmation?
J'ai fait de la lecture ( HTML considéré comme une langue de programmation? , Turing complet et Et comment puis-je déterminer si quelque chose est Turing complet ? Y a-t-il des critères spécifiques?
a le contrôle de structures de contrôle (relevés conditionnels et boucles) suffisamment pour être considéré Turing complet ?
4 Réponses :
Le terme "langage de programmation" est quelque peu flou. Les expressions régulières constituent-elles un langage de programmation? La plupart des programmeurs diraient oui, même si les regexnes ne sont pas terminés.
En ce qui concerne l'exhaustivité de Turing, je ne suis pas un expert, mais je pense qu'il suffit de disposer d'une branche conditionnelle et d'une pile infinie (donc une véritable machine seulement de l'exhaustivité de Turning).
EDIT: Après un peu de recherche, j'ai constaté que cela ne suffit pas. Vous avez besoin d'au moins deux piles et d'un nombre minimal d'états (et d'une table de transition d'état).
Peut-être qu'un critère plus bas à terre est que si vous souvenez peut-être des quantités arbitraires d'état et des boucles, il est probablement Turing complet.
Il existe des langages de programmation qui ne sont pas terminés. Pour quelques exemples de langues complètes de non-Turing, jetez un coup d'œil à: Langues pratiques non-Turing-complètes ?
Un avantage d'avoir une langue non-turicing complète pourrait par exemple être que cela pourrait être suffisant pour effectuer les tâches dont vous avez besoin, tout en étant assez simple pour vous permettre de prouver des propriétés de vos programmes, ce que vous ne pouviez pas autrement prouver. Cela pourrait, par exemple, être utile dans les cas où il est essentiel de savoir que le programme fonctionnera sans erreur.
Qu'est-ce qui constitue exactement un langage de programmation est un peu vague, mais on pourrait dire que c'est une langue dans laquelle vous pouvez exprimer des calculs. Si nous regardons HTML, vous ne pouvez pas créer de document qui calcule. Il ne dit que le navigateur comment la page est censée regarder. La partie importante à noter est, elle ne calcule rien de nouveau.
C'est, comme le dit Marcelo, assez flou.
Quant à la détermination Si une langue est Turing complète, je vous référerai à cette question: Quelles sont les lignes directrices pratiques pour évaluer" l'exhaustivité en tucelle "de la langue?
Un programme fonctionnel ne calcule rien; Il dit à quel point le résultat devrait être. Il en va de même pour les langages de programmation logique comme Prolog. Du point de vue de la théorie des langues, la seule condition requise pour un langage de programmation est qu'il existe une grammaire sans ambiguïté pour cela, il existe donc une structure syntaxique unique pour toute séquence valide. La signification de ladite structure est à la hauteur de l'interprète ou du traducteur; Une jolie imprimante, un analyseur de métriques et un compilateur, donnent des significations différentes au même programme (une jolie imprimante ne se soucie pas des types et des opérations incompatibles, F.I.).
Le protocole TCP est un langage de programmation.
Quels sont les critères ou les fonctionnalités de base nécessaires pour indiquer que x ou y est (ou non) une langue de programmation?
Comme Marcelo Cantos a déjà dit qu'il est quelque peu floue, d'autant plus qu'il existe des langues spécifiques à un domaine (DSLS; http://en.wikipedia.org/wiki/domain-specific_Language ) qui ne sont pas terminés, mais aussi souvent considérés comme des langages de programmation.
Et comment puis-je déterminer si quelque chose est Turing complet? Y a-t-il des critères spécifiques?
Un moyen de déterminer si un langage de programmation est Turing complet consiste à écrire une machine de Turing en elle (ou une mise en œuvre du calcul de la Lambda).
Un autre moyen est de prouver que toutes les fonctions mu-récursives 0 commentaires
Pensons donc aux conséquences de ces définitions concrètes:
Un langage Turing-complet est une langue de programmation: CSS devient une langue de programmation .
Un langage de programmation doit être terminé: peut-être, mais Les programmes peuvent être écrits autrement .
Maintenant une définition beaucoup meilleure: Un langage de programmation est celui qui peut être utilisé pour écrire des programmes .