Une langue peut-elle être complète mais incomplète d'une autre manière?

Question

Par exemple, lors de l'écriture d'un système d'exploitation, y a-t-il des choses qui ne peuvent pas être accomplies dans un langage complet?

Answer 1

Non. ou du moins, si vous en trouviez une qui réfute la Thèse Church Turing .

Cependant, il existe des langages qui sont complets et dans lesquels il est très pénible d’écrire certains programmes, comme le traitement de chaînes en FORTRAN, la programmation numérique en COBOL, l’arithmétique des nombres entiers dans sed, pratiquement tout en assembleur x86 .

Et bien sûr, il existe brainfuck .

Answer 2

Oui, vous pouvez avoir un langage qui ne vous permet pas de manipuler le matériel directement. Il serait difficile d'écrire un système d'exploitation à l'aide du shell Bourne, par exemple. Mais ces limitations sont moins importantes que vous ne le pensez. Les systèmes d'exploitation ont été écrits en Standard ML, Scheme et même Haskell !

Answer 3

Turing-complete est la définition formelle la plus générale de la complétude. Certaines fonctionnalités linguistiques sont nécessaires pour certaines applications, mais elles ne rentrent pas dans les définitions formelles.

Par exemple, les fonctionnalités graphiques, la capacité de générer des processus en arrière-plan, la capacité de conserver l'état persistant et la capacité de se connecter au réseau sont des fonctionnalités utiles, mais ne concernent pas la complétude de Turing d'un langage. Donc, Python sur Google App Engine ou une applet Java s'exécutant dans un sandbox reste Turing-complete.

Vous remarquerez que dans de nombreux cas, ces types de fonctionnalités sont fournis par les bibliothèques plutôt que par le langage principal.

Answer 4

Si vous parlez de pragmatique, alors bien sûr ... vous pouvez imaginer un langage de programmation sans capacité de lire ou d'écrire des fichiers (par exemple, un langage qui permet de calculer n'importe quelle fonction sur des entiers mais c'est tout) ... Le fait qu'un langage ne puisse pas fonctionner avec mon grille-pain ne signifie pas qu'il n'est pas Turing-complete, mais signifie aussi qu'il y a des choses qu'il ne peut pas faire . Je ne suis donc pas sûr de l'importance ou de l'utilité de cette distinction. .

Answer 5

En fonction du contexte, "accomplir quelque chose dans une langue" signifie différentes choses pour différentes personnes. Turing est l’une de ces personnes et il a défini très précisément ce qu’il entend par "complet".

Si un langage (ou une machine théorique) est complet de Turing, aucun calcul de Turing ne peut être fait. Cela ne veut pas dire que le langage est tout-puissant, mais qu’il est bon en somme. Il y a beaucoup de " choses " qui ne sont pas des calculs de Turing et qu’un ordinateur complet de Turing peut donc ne pas être en mesure de faire.

"Être un système d'exploitation" n'est pas un calcul de Turing. Pour être un système d'exploitation, vous devez faire plus que des calculs. Vous devez également manipuler le matériel.

Avec un langage complet de Turing et un ensemble d’opérations permettant de manipuler le matériel dont vous avez besoin, y compris un concept d’entrée et de temps adapté, vous pouvez écrire un système d’exploitation. Ou devrais-je dire, il est possible d'écrire un système d'exploitation. Cela dépend de la facilité d'utilisation du langage et des limitations physiques ignorées par la définition de Turing, telles que la capacité du programme résultant à tenir et à s'exécuter dans la mémoire du périphérique que vous souhaitez utiliser, et courez dans un temps réaliste.

Ignorant les limitations pratiques, vous pouvez écrire un système d’exploitation dans n’importe quel langage complet de Turing, à condition que le langage comporte également suffisamment d’opérations pour piloter le matériel. "Appels de bibliothèque", si vous souhaitez adopter l'approche pratique CS consistant à distinguer le langage des bibliothèques. Turing n’a pas fait cette distinction, car son modèle informatique n’a pas le concept d’un "appel". en tous cas. Vous devez également résoudre le problème de démarrage: votre matériel doit exécuter directement le langage que vous écrivez, ou vous avez besoin d’un compilateur dans une langue que le matériel utilise, ou bien vous avez besoin d’un interprète écrit dans une langue que le le matériel fonctionne. Encore une fois, Turing ignore tout cela parce que son modèle de calcul utilise un matériel abstrait, alors que l’écriture d’un système d’exploitation est une affaire de matériel.

En anglais (plutôt que CompSciSpeak), il est courant de dire qu’une langue "manque de certaines fonctionnalités" et peut-être même qu’elle est "incomplète". par comparaison avec une autre langue qui les a. On pourrait également soutenir qu'il est possible d'implémenter des fermetures en C. On peut par exemple écrire un programme C interpréteur Lisp et y intégrer un programme Lisp sous forme de chaîne. Voilà, les fermetures en C. Cependant, ce n'est pas ce que la plupart des gens demandent s'ils disent: "J'aimerais que C ait des fermetures". Si vous pensez que chaque langue a besoin de fermetures, alors C est incomplet. Si vous pensez que chaque langue a besoin d’une programmation structurée, l’assembleur ARM est incomplet. Si vous pensez qu'il est possible d'ajouter dynamiquement des méthodes à un objet, C ++ est incomplet, même s'il est parfaitement possible d'écrire une classe C ++ avec l'option "AddMethod". et "CallMethodByName". méthodes et fake votre propre convention d'appel de méthode à partir de là. Etc.

Turing ne pense pas que les langues ont besoin de ces commodités: elles n’affectent pas les calculs pouvant être effectués, mais aussi la facilité avec laquelle il est possible d’écrire certains programmes. Le concept de complétude de Turing ne dit rien sur ce à quoi ressemblent les programmes, ni sur la manière dont ils sont organisés, seulement ce qu’ils produisent. Ces langues sont donc complètes, mais du point de vue du programmeur, certaines choses ne peuvent être accomplies dans ces langues.

Answer 6

Le langage peut ou ne peut pas faire des choses comme - sous-routines, récursivité, types de données personnalisés, boucles, définition de classes, goto, etc. L'ensemble de ces fonctionnalités de langage le complète ou non. Par exemple, la langue est incomplète si vous n'avez pas de boucles, gotos et sous-programmes - vous ne pouvez effectuer aucune opération cyclique. La complétude du langage est une chose très théorique et scientifique. Comme par exemple, il est prouvé que même si votre langage ne permet pas d’appeler des fonctions de manière récursive, mais autorise les pointeurs de fonction, vous pouvez simuler une récursivité, c’est-à-dire avec y-combinator.

Des choses comme travailler avec des fichiers et du matériel ne font pas souvent partie du langage. Pour accomplir toute tâche de programmation, vous avez besoin de plus que du langage. Vous avez besoin de l’environnement dans lequel votre programme fonctionne. En x86 en tant que langue, vous disposez des instructions " int " avec un seul paramètre, mais il appartient au système d’exécuter certaines opérations lorsque vous exécutez "int 21h".

La langue a juste besoin d’un moyen de communiquer avec l’environnement et d’être complète - c’est ensuite à l’environnement de l’utiliser. Il est valide d’écrire en x86 asm " mov ax, bx " mais il appartient à votre processeur d'effectuer cette opération.

Étant incomplet d’une autre manière - facile, définissez simplement votre propre version de l’exhaustivité. c'est-à-dire que je n'aime pas travailler sans la POO basée sur les classes, définissons donc ce langage n'est pas complet de Feldman s'il ne dispose pas de fonctionnalités de langage prenant en charge la POO basée sur des classes. Ok, C et Javascript n’est pas complet. Vous pouvez toujours faire quelque chose dans ces langues et même simuler la POO basée sur les classes à un certain niveau.

En ce qui concerne le système d'exploitation, vous avez toujours besoin d'un processeur qui exécute des instructions et d'un compilateur qui traduit la langue en instructions de la CPU. Je peux imaginer que le compilateur traduise n'importe quoi en codes de machines. Par exemple, ce qui suit est un code JS valide

for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

et il ne devrait pas être si difficile de le compiler en code machine.

Dans le monde moderne, vous choisissez non seulement la langue, mais également la plate-forme, les bibliothèques standard et non standard, la littérature, la communauté, le support, etc. Toutes ces choses affectent votre capacité à faire certaines choses, et elles peuvent être prises peut-être pas "assez complet" pour votre tâche. Mais si je ne peux pas compiler le code c ++ en applet java, cela ne signifie pas qu’il s’agit d’une incomplétude du langage c ++. C'est juste l'absence de compilateur qui transformera le code c ++ en quelque chose qui peut être chargé par JVM.

Si vous le souhaitez, vous pouvez concevoir une langue avec des fonctionnalités telles que "OpenFile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards". Mais si le langage ne les utilise pas, elles peuvent toujours être implémentées avec d'autres fonctionnalités de langage et de prise en charge de l'environnement. Par conséquent, l'absence de telles fonctionnalités ne rend pas le langage incomplet. Si votre langage est similaire à C, mais sans opérateur goto, opérateur de boucle (for, while, do while) et fonctions, vous ne pouvez pas écrire de programme cyclique et aucun environnement ni aucune bibliothèque ne peut vous aider.

Answer 7

La réponse est un oui très clair. L'exhaustivité de Turing implique uniquement qu'un langage complet de Turing peut être utilisé pour calculer toute fonction calculable. D'une part, cela ne dit rien sur la complexité d'un calcul.

Vous pouvez généralement vous attendre à ce que tout algorithme temporel polynomial puisse être exprimé sous la forme d'un algorithme temporel polynomial dans tout autre langage complet de Turing, mais c'est à peu près tout. Particulièrement toutes les exigences en temps réel (soft ou hard) vont au-delà de la fenêtre si votre seul objectif est la complétude de Turing.

Un autre élément important est l’expression d’un langage, qui est en grande partie une propriété subjective, mais vous pouvez comprendre que les programmes sont beaucoup plus difficiles à écrire dans un code machine que, par exemple, Java.

Comme pour les systèmes d’exploitation, une interface avec le matériel est indispensable, mais tout langage peut être équipé de tels utilitaires.

[Modifier] Une autre chose que je pourrais ajouter est qu’aucune implémentation réelle d’un langage de programmation n’est complète par la nature de nos machines informatiques finies. Alors que la thèse de Church-Turing, ainsi que les découvertes fondamentales (comme le problème qui pose problème), jettent les bases de notre compréhension de l’informatique, elles rencontrent rarement le monde de l’informatique pratique.

Answer 8

Facilité d'utilisation incomplète:)

Answer 9

Quand on parle de langues, on suppose généralement que les langues fonctionnent sur des machines très simples. En tant que tel, aucun concept de lecture d’un fichier ou d’accès au réseau n’est normalement pris en compte en ce qui concerne la puissance d’une langue.

Il existe différentes classes de langages qui sont souvent utilisés dans la théorie de la calculabilité (chacune avec des modifications presque infinies)

1. Automate fini. C'est la classe de machines la plus simple et elles peuvent reconnaître la plus petite classe de langages, qui sont les exactes langues que les expressions régulières peuvent reconnaître, c'est-à-dire. si une chaîne commence par deux 'a et se termine par d. Ils ne peuvent pas être utilisés pour reconnaître si une chaîne contient un ensemble équilibré de parenthèses, fx.
2. Abaissez l'automate. Ceci est essentiellement une extension des automates finis avec une pile. Contrairement aux machines à états finis, elles peuvent être utilisées pour déterminer si une chaîne particulière contient un ensemble équilibré de parenthèses. Les langages que les automates enfoncés peuvent reconnaître sont exactement l'ensemble qui peut être décrit à l'aide de grammaires sans contexte et ils sont souvent utilisés pour analyser le code source.
3. Machines de Turing. Il s’agit des machines les plus puissantes de la catégorie, mais cela ne signifie pas qu’elles peuvent être utilisées pour répondre à toutes les questions. Ils sont incapables de répondre à la question. Cette chaîne décrit-elle une machine de Turing qui fonctionnera pour toujours? En fait, aucune machine de Turing ne peut en dire plus sur les propriétés non triviales de toute machine de Turing (théorème du riz).

Alors oui, une machine de Turing a des limites, et il existe des classes de machines qui peuvent faire quelque chose qu'une machine de Turing ne peut pas, mais elles n’ont jamais existé (en théorie), mais plus récemment en pratique.

Answer 10

Je ne pense pas que les définitions de complétude autres que Turing (ou les expressions régulières, ou les automates déroulants) soient pertinentes pour les langues . Mais cette exhaustivité ne concerne que les installations informatiques numériques ou symboliques.

Les choses que vous mentionnez me paraissent être davantage fonction du moteur d’exécution et de l’environnement que du langage. Il existe une distinction importante et les notions formelles de complétude ne s'appliquent généralement qu'aux langues elles-mêmes.