Complétude de Turing

La complétude de Turing est importante car elle signifie que toute conception concrète d'un dispositif informatique peut être simulée par une machine de Turing universelle . La thèse de Church-Turing affirme qu'il s'agit d'une loi mathématique : une machine de Turing universelle peut, en principe, effectuer n'importe quel calcul qu'un ordinateur programmable peut réaliser. Ceci ne dit rien de l'effort nécessaire à la programmation , du temps d'exécution de la machine, ni des capacités non liées au calcul que cette dernière pourrait posséder.

La machine analytique de Charles Babbage (années 1830) aurait été la première machine de Turing-complète si elle avait été construite à l'époque de sa conception. Babbage reconnaissait que la machine était capable de réaliser des prouesses de calcul, notamment un raisonnement logique primitif, mais il ignorait qu'aucune autre machine ne pouvait faire mieux. Des années 1830 aux années 1940, des machines à calculer mécaniques, telles que des additionneurs et des multiplicateurs, furent construites et améliorées, mais elles ne pouvaient pas effectuer de branchement conditionnel et n'étaient donc pas de Turing-complètes.Leopold Kronecker formula la notion de calculabilité, définissant les fonctions récursives primitives . Ces fonctions peuvent être calculées par automatisme, mais elles ne suffisent pas à la création d'un ordinateur universel, car les instructions qui les calculent ne permettent pas de boucle infinie. Au début du XXe siècle, David Hilbert dirigea un programme visant à axiomatiser l'ensemble des mathématiques à l'aide d'axiomes précis et de règles de déduction logiques précises, exécutables par une machine. Il apparut rapidement qu'un petit ensemble de règles de déduction suffisait à produire les conséquences de n'importe quel ensemble d'axiomes. Kurt Gödel démontra en 1930 que ces règles suffisaient à démontrer tout théorème.

La notion même de calcul a été isolée peu après, à commencer par le théorème d'incomplétude de Gödel . Ce théorème a démontré que les systèmes d'axiomes étaient limités lorsqu'il s'agissait de raisonner sur le calcul qui déduit leurs théorèmes. Church et Turing ont démontré indépendamment que le problème de décision de Hilbert était insoluble , identifiant ainsi le noyau calculatoire du théorème d'incomplétude. Ces travaux, ainsi que ceux de Gödel sur les fonctions récursives générales , ont établi l'existence d'ensembles d'instructions simples qui, combinés, permettent de réaliser n'importe quel calcul. Les travaux de Gödel ont démontré que la notion de calcul est fondamentalement unique.

En 1941, Konrad Zuse acheva l' ordinateur Z3 . À cette époque, Zuse ignorait les travaux de Turing sur la calculabilité. En particulier, le Z3 ne disposait pas de mécanismes dédiés aux sauts conditionnels, ce qui l'empêchait d'être Turing-complet. Cependant, en 1998, Rojas a démontré que le Z3 était capable de simuler des sauts conditionnels et, par conséquent, Turing-complet en théorie. Pour ce faire, son programme sur bande magnétique devait être suffisamment long pour exécuter tous les chemins possibles dans les deux sens de chaque branche.

Le premier ordinateur capable de branchement conditionnel en pratique, et donc Turing-complet en pratique, fut l' ENIAC en 1946. L'ordinateur Z4 de Zuse était opérationnel en 1945, mais il ne prenait pas en charge le branchement conditionnel avant 1950.

La théorie de la calculabilité utilise des modèles de calcul pour analyser les problèmes et déterminer s'ils sont calculables et dans quelles circonstances. Son premier résultat est qu'il existe des problèmes pour lesquels il est impossible de prédire le comportement d'un système (Turing-complet) sur une durée arbitrairement longue.

L'exemple classique est le problème de l'arrêt : concevoir un algorithme qui prend en entrée un programme écrit dans un langage Turing-complet et des données destinées à ce programme, et qui détermine si ce dernier, traité par ces données, finira par s'arrêter ou s'il continuera indéfiniment. Il est trivial de concevoir un algorithme capable de résoudre ce problème pour certaines entrées, mais impossible de le faire en général. Pour toute caractéristique de la sortie finale du programme, il est impossible de déterminer si cette caractéristique sera vérifiée.

Cette impossibilité pose problème lors de l'analyse de programmes informatiques réels. Par exemple, il est impossible de concevoir un outil qui protège entièrement les programmeurs contre l'écriture de boucles infinies ou les utilisateurs contre la saisie de données susceptibles de provoquer de telles boucles.

On peut limiter l'exécution d'un programme à une durée fixe ( délai d'expiration ) ou restreindre la puissance des instructions de contrôle de flux (par exemple, en n'autorisant que les boucles parcourant les éléments d'un tableau existant). Cependant, un autre théorème démontre l'existence de problèmes résolubles par des langages Turing-complets, mais insolubles par tout langage aux capacités de boucle finies (c'est-à-dire les langages garantissant l'arrêt de tout programme). Un tel langage n'est donc pas Turing-complet. Par exemple, un langage garantissant l'arrêt des programmes ne peut calculer la fonction calculable obtenue par l'argument diagonal de Cantor appliqué à l'ensemble des fonctions calculables de ce langage.

Les systèmes de calcul (algèbres, calculs) considérés comme Turing-complets sont ceux destinés à l'étude de l'informatique théorique . Ils se veulent aussi simples que possible, afin de faciliter la compréhension des limites du calcul. En voici quelques exemples :

• Théorie des automates
• Grammaire formelle (générateurs de langage)
• Langage formel (reconnaissance du langage)
• lambda-calcul
• Machines post-Turing
• calcul de processus

La plupart des langages de programmation (leurs modèles abstraits, éventuellement omis en raison de certaines constructions particulières supposant une mémoire finie), conventionnels et non conventionnels, sont Turing-complets. Cela inclut :

• Toutes les langues d'usage général largement répandues.
  • Langages de programmation procédurale tels que C , Pascal .
  • Les langages orientés objet tels que Java , Smalltalk ou C# .
  • Langages multi-paradigmes tels que Ada , C++ , Common Lisp , Fortran , JavaScript , Object Pascal , Perl , Python , R.
• La plupart des langues utilisant des paradigmes moins courants :
  • Les langages fonctionnels tels que Lisp et Haskell .
  • Les langages de programmation logique tels que Prolog .
  • Processeur macro à usage général tel que le m4 .
  • Les langages déclaratifs tels que SQL et XSLT .
  • VHDL et autres langages de description de matériel.
  • TeX , un système de composition typographique.
  • Les langages de programmation ésotériques sont une forme de récréation mathématique dans laquelle les programmeurs cherchent à réaliser des constructions de programmation de base dans un langage extrêmement difficile mais mathématiquement équivalent à une machine de Turing.

Certains systèmes de réécriture sont Turing-complets.

La complétude de Turing est une affirmation abstraite de capacité, plutôt qu'une prescription de fonctionnalités spécifiques du langage utilisées pour implémenter cette capacité. Les fonctionnalités utilisées pour atteindre la complétude de Turing peuvent être très différentes ; les systèmes Fortran utilisent des boucles ou éventuellement des instructions goto pour réaliser la répétition ; Haskell et Prolog, qui ne prennent pratiquement pas en charge les boucles, utilisent la récursivité . La plupart des langages de programmation décrivent des calculs sur des architectures de von Neumann , qui possèdent de la mémoire (RAM et registres) et une unité de contrôle. Ces deux éléments rendent cette architecture Turing-complète. Même les langages purement fonctionnels sont Turing-complets.

La complétude de Turing en SQL déclaratif est implémentée grâce aux expressions de table communes récursives . Sans surprise, les extensions procédurales de SQL ( PLSQL , etc.) sont également Turing-complètes. Ceci illustre une des raisons pour lesquelles les langages relativement puissants non Turing-complets sont rares : plus un langage est puissant initialement, plus les tâches auxquelles il s’applique sont complexes et plus son manque de complétude est rapidement perçu comme un inconvénient, encourageant ainsi son extension jusqu’à ce qu’il devienne Turing-complet.

Le lambda-calcul non typé est Turing-complet, mais de nombreux lambda-calculs typés, dont le Système F , ne le sont pas. L'intérêt des systèmes typés réside dans leur capacité à représenter la plupart des programmes informatiques courants tout en détectant davantage d'erreurs.

La règle 110 et le jeu de la vie de Conway , tous deux des automates cellulaires , sont Turing-complets.

Il existe de nombreux langages informatiques qui ne sont pas Turing-complets. On peut citer l'exemple des langages réguliers , générés par des expressions régulières et reconnus par des automates finis . Une extension plus puissante, mais toujours non Turing-complète, des automates finis est la catégorie des automates à pile et des grammaires hors contexte , couramment utilisées pour générer les arbres d'analyse syntaxique lors de la compilation initiale d'un programme . Parmi les autres exemples, on peut mentionner certaines versions anciennes des langages de shaders de pixels intégrés aux extensions Direct3D et OpenGL .de programmation fonctionnelle totale , tels que Epigram , toutes les fonctions sont totales et doivent se terminer. Charity utilise un système de types et des constructions de contrôle basés sur la théorie des catégories , tandis qu'Epigram utilise des types dépendants . Le langage LOOP est conçu pour calculer uniquement les fonctions récursives primitives . Ces dernières calculent toutes des sous-ensembles propres de l'ensemble total des fonctions calculables, car cet ensemble n'est pas calculable et énumérable . De plus, comme toutes les fonctions de ces langages sont totales, il est impossible d'écrire des algorithmes pour les ensembles récursivement énumérables dans ces langages, contrairement aux machines de Turing.

Bien que le lambda-calcul (non typé) soit Turing-complet, le lambda-calcul simplement typé ne l'est pas.