Complétude de Turing - Turing completeness

Dans la théorie de la calculabilité , un système de règles de manipulation de données (comme le jeu d' instructions d' un ordinateur , un langage de programmation ou un automate cellulaire ) est dit Turing-complet ou informatiquement universel s'il peut être utilisé pour simuler n'importe quelle machine de Turing . Cela signifie que ce système est capable de reconnaître ou de décider d'autres ensembles de règles de manipulation de données. L'exhaustivité de Turing est utilisée comme un moyen d'exprimer la puissance d'un tel ensemble de règles de manipulation de données. Pratiquement tous les langages de programmation actuels sont Turing-complets. Le concept porte le nom du mathématicien et informaticien anglais Alan Turing .

Un concept connexe est celui de l' équivalence de Turing  - deux ordinateurs P et Q sont appelés équivalents si P peut simuler Q et Q peut simuler P. La thèse de Church-Turing conjecture que toute fonction dont les valeurs peuvent être calculées par un algorithme peut être calculée par un machine de Turing, et donc que si n'importe quel ordinateur du monde réel peut simuler une machine de Turing, c'est l'équivalent d'une machine de Turing. Une machine de Turing universelle peut être utilisée pour simuler n'importe quelle machine de Turing et par extension les aspects informatiques de n'importe quel ordinateur réel possible.

Pour montrer que quelque chose est Turing-complet, il suffit de montrer qu'il peut être utilisé pour simuler un système Turing-complet. Par exemple, un langage impératif est Turing-complet s'il a un branchement conditionnel (par exemple, des instructions "if" et "goto", ou une instruction "branche si zéro"; voir un jeu d'instructions ordinateur ) et la possibilité de changer un quantité de mémoire (par exemple, la capacité de maintenir un nombre arbitraire d'éléments de données). Bien entendu, aucun système physique ne peut avoir une mémoire infinie ; mais si la limitation de la mémoire finie est ignorée, la plupart des langages de programmation sont autrement Turing-complets.

Utilisation non mathématique

En dialectal l' utilisation, les termes « Turing-complet » et « Turing-équivalent » sont utilisés pour signifier que tous les ordinateurs dans le monde réel à usage général ou un langage informatique peut environ simuler les aspects informatiques de tout autre ordinateur monde réel usage général ou Langage informatique.

Les vrais ordinateurs construits jusqu'à présent peuvent être analysés fonctionnellement comme une machine de Turing à une seule bande (la « bande » correspondant à leur mémoire) ; ainsi les mathématiques associées peuvent s'appliquer en faisant abstraction de leur fonctionnement assez loin. Cependant, les ordinateurs réels ont des ressources physiques limitées, ils ne sont donc que des automates linéaires limités complets. En revanche, un ordinateur universel est défini comme un appareil avec un jeu d'instructions complet de Turing, une mémoire infinie et un temps disponible infini.

Définitions formelles

Dans la théorie de la calculabilité , plusieurs termes étroitement liés sont utilisés pour décrire la puissance de calcul d'un système de calcul (comme une machine abstraite ou un langage de programmation ):

Complétude de Turing
Un système de calcul qui peut calculer chaque fonction calculable de Turing est appelé Turing-complet (ou Turing-puissant). Alternativement, un tel système est celui qui peut simuler une machine de Turing universelle .
Équivalence de Turing
Un système Turing-complet est appelé Turing-équivalent si chaque fonction qu'il peut calculer est également Turing-calculable ; c'est-à-dire qu'il calcule précisément la même classe de fonctions que les machines de Turing . Alternativement, un système équivalent à Turing est un système qui peut simuler et être simulé par une machine de Turing universelle. (Tous les systèmes complets de Turing physiquement implémentables sont équivalents à Turing, ce qui ajoute un support à la thèse Church-Turing .)
Universalité (informatique)
Un système est dit universel par rapport à une classe de systèmes s'il peut calculer toutes les fonctions calculables par les systèmes de cette classe (ou peut simuler chacun de ces systèmes). Typiquement, le terme d'universalité est tacitement utilisé par rapport à une classe de systèmes Turing-complet. Le terme « faiblement universel » est parfois utilisé pour distinguer un système (par exemple un automate cellulaire ) dont l'universalité n'est atteinte qu'en modifiant la définition standard de la machine de Turing de manière à inclure des flux d'entrée avec une infinité de 1 .

Histoire

Turing-complet est important que chaque conception du monde réel pour un dispositif informatique peut être simulé par une machine de Turing universelle . La Thèse de Church stipule que c'est une loi des mathématiques - qu'une machine de Turing universelle peut, en principe, effectuer tout calcul que tout autre programmable ordinateur peut. Cela ne dit rien sur l'effort nécessaire pour écrire le programme , ou le temps que la machine peut prendre pour effectuer le calcul, ou les capacités que la machine peut posséder qui n'ont rien à voir avec le calcul.

Le moteur analytique de Charles Babbage (années 1830) aurait été la première machine complète de Turing s'il avait été construit au moment de sa conception. Babbage appréciait que la machine soit capable de grands exploits de calcul, y compris le raisonnement logique primitif, mais il n'appréciait pas qu'aucune autre machine ne puisse faire mieux. Des années 1830 aux années 1940, des machines à calculer mécaniques telles que des additionneurs et des multiplicateurs ont été construites et améliorées, mais elles ne pouvaient pas effectuer de branchement conditionnel et n'étaient donc pas Turing-complets.

À la fin du XIXe siècle, Leopold Kronecker a formulé des notions de calculabilité, définissant des fonctions récursives primitives . Ces fonctions peuvent être calculées par cœur, mais elles ne suffisent pas à faire un ordinateur universel, car les instructions qui les calculent ne permettent pas une boucle infinie. Au début du 20e siècle, David Hilbert a dirigé un programme visant à axiomatiser toutes les mathématiques avec des axiomes précis et des règles logiques de déduction précises qui pourraient être exécutées par une machine. Bientôt, il devint clair qu'un petit ensemble de règles de déduction suffisait pour produire les conséquences de n'importe quel ensemble d'axiomes. Ces règles ont été prouvées par Kurt Gödel en 1930 pour être suffisantes pour produire tous les théorèmes.

La notion même de calcul a été isolée peu de temps après, en commençant par le théorème d'incomplétude de Gödel . Ce théorème a montré que les systèmes d'axiomes étaient limités lors du raisonnement sur le calcul qui en déduit leurs théorèmes. Church et Turing ont indépendamment démontré que le problème d' Entscheidungs (problème de décision) de Hilbert était insoluble, identifiant ainsi le noyau informatique du théorème d'incomplétude. Ce travail, ainsi que les travaux de Gödel sur les fonctions récursives générales , ont établi qu'il existe des ensembles d'instructions simples qui, une fois assemblées, sont capables de produire n'importe quel calcul. Les travaux de Gödel ont montré que la notion de calcul est essentiellement unique.

En 1941, Konrad Zuse acheva l' ordinateur Z3 . Zuse n'était pas familier avec les travaux de Turing sur la calculabilité à l'époque. En particulier, le Z3 manquait d'installations dédiées pour un saut conditionnel, l'empêchant ainsi d'être Turing complet. Cependant, en 1998, il a été démontré par Rojas que le Z3 est capable de sauts conditionnels, et donc de Turing complet, en utilisant certaines de ses fonctionnalités de manière non intentionnelle.

Théorie de la calculabilité

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. Le premier résultat de la théorie de la calculabilité est qu'il existe des problèmes pour lesquels il est impossible de prédire ce que fera un système (complet de Turing) sur un temps arbitrairement long.

L'exemple classique est le problème de l' arrêt : créer un algorithme qui prend en entrée un programme dans un langage Turing-complet et des données à fournir à ce programme, et détermine si le programme, opérant sur l'entrée, finira par s'arrêter ou continuera pour toujours. Il est trivial de créer un algorithme qui puisse le faire pour certaines entrées, mais impossible de le faire en général. Pour toute caractéristique de la sortie éventuelle du programme, il est impossible de déterminer si cette caractéristique se tiendra.

Cette impossibilité pose des problèmes lors de l'analyse de programmes informatiques réels. Par exemple, on ne peut pas écrire un outil qui protège entièrement les programmeurs d'écrire des boucles infinies ou protège les utilisateurs de fournir des entrées qui provoqueraient des boucles infinies.

On peut à la place limiter un programme à s'exécuter uniquement pendant une période de temps fixe ( timeout ) ou limiter la puissance des instructions de contrôle de flux (par exemple, en ne fournissant que des boucles qui itèrent sur les éléments d'un tableau existant). Cependant, un autre théorème montre qu'il existe des problèmes résolvables par les langages complets de Turing qui ne peuvent être résolus par aucun langage avec seulement des capacités de boucle finies (c'est-à-dire tout langage garantissant que chaque programme finira par s'arrêter). Donc, un tel langage n'est pas Turing-complet. Par exemple, un langage dans lequel les programmes sont garantis pour se terminer et s'arrêter ne peut pas calculer la fonction calculable produite par l'argument diagonal de Cantor sur toutes les fonctions calculables dans ce langage.

Oracles de Turing

Un ordinateur ayant accès à une bande infinie de données peut être plus puissant qu'une machine de Turing : par exemple, la bande peut contenir la solution au problème de l' arrêt ou à un autre problème Turing indécidable. Une telle bande infinie de données s'appelle un oracle de Turing . Même un oracle de Turing avec des données aléatoires n'est pas calculable ( avec probabilité 1 ), car il n'y a qu'un nombre dénombrable de calculs mais un nombre indénombrable d'oracles. Ainsi, un ordinateur avec un oracle de Turing aléatoire peut calculer des choses qu'une machine de Turing ne peut pas.

Physique numérique

Toutes les lois connues de la physique ont des conséquences calculables par une série d'approximations sur un ordinateur numérique. Une hypothèse appelée physique numérique affirme que ce n'est pas un accident car l' univers lui-même est calculable sur une machine de Turing universelle. Cela impliquerait qu'aucun ordinateur plus puissant qu'une machine de Turing universelle ne peut être construit physiquement.

Exemples

Les systèmes informatiques (algèbres, calculs) qui sont considérés comme des systèmes complets de Turing sont ceux destinés à l'étude de l'informatique théorique . Ils se veulent aussi simples que possible, afin qu'il soit plus facile de comprendre les limites du calcul. Voici quelques-uns:

La plupart des langages de programmation (leurs modèles abstraits, peut-être avec certaines constructions particulières qui supposent l'omission de la mémoire finie), conventionnels et non conventionnels, sont Turing-complets. Ceci comprend:

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

L'exhaustivité de Turing est une déclaration abstraite de capacité, plutôt qu'une prescription de caractéristiques linguistiques spécifiques utilisées pour mettre en œuvre cette capacité. Les fonctionnalités utilisées pour atteindre l'exhaustivité de Turing peuvent être très différentes ; Les systèmes Fortran utiliseraient des constructions en boucle ou peut-être même des instructions goto pour réaliser la répétition ; Haskell et Prolog, manquant presque entièrement de boucle, utiliseraient la récursivité . La plupart des langages de programmation décrivent des calculs sur des architectures de von Neumann , qui ont de la mémoire (RAM et registre) et une unité de contrôle. Ces deux éléments rendent cette architecture Turing-complète. Même les langages fonctionnels purs sont Turing-complets.

L'exhaustivité de Turing en SQL déclaratif est implémentée via des expressions de table communes récursives . Sans surprise, les extensions procédurales à SQL ( PLSQL , etc.) sont également Turing-complets. Ceci illustre une des raisons pour lesquelles les langages non-complets de Turing relativement puissants sont rares : plus le langage est puissant au départ, plus les tâches auxquelles il est appliqué sont complexes et plus tôt son manque d'exhaustivité devient perçu comme un inconvénient, encourageant son extension jusqu'à ce qu'il soit Turing-complet.

Le calcul lambda non typé est Turing-complet, mais de nombreux calculs lambda typés, y compris System F , ne le sont pas. La valeur des systèmes typés repose sur leur capacité à représenter la plupart des programmes informatiques typiques 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.

Complétude de Turing non intentionnelle

Certains jeux et autres logiciels sont Turing-complets par accident, c'est-à-dire pas par conception.

Logiciel:

Jeux vidéo:

Des médias sociaux:

Jeux de cartes:

Jeux à personne zéro (simulations) :

Langages de calcul :

Matériel informatique:

  • instruction MOV x86

La biologie:

Langues non complètes de Turing

Il existe de nombreux langages de calcul qui ne sont pas Turing-complets. Un tel exemple est l'ensemble des langages réguliers , qui sont générés par des expressions régulières et qui sont reconnus par des automates finis . Une extension plus puissante mais toujours pas complète de Turing des automates finis est la catégorie des automates à refoulement et des grammaires sans contexte , qui sont couramment utilisées pour générer des arbres d'analyse dans une étape initiale de la compilation du programme . D'autres exemples incluent certaines des premières versions des langages de pixel shader intégrés dans les extensions Direct3D et OpenGL .

Dans les langages de programmation fonctionnels totaux , tels que Charity et Epigram , toutes les fonctions sont totales et doivent se terminer. Charity utilise un système de types et des constructions de contrôle basées sur la théorie des catégories , tandis qu'Epigram utilise des types dépendants . Le langage LOOP est conçu de manière à ne calculer que les fonctions primitives récursives . Tous ces éléments calculent des sous-ensembles appropriés des fonctions calculables totales, car l'ensemble complet des fonctions calculables totales n'est pas énumérable par calcul . De plus, puisque toutes les fonctions de ces langages sont totales, les algorithmes pour les ensembles récursivement énumérables ne peuvent pas être écrits 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.

Langages de données

La notion de complétude de Turing ne s'applique pas aux langages tels que XML , HTML , JSON et YAML , car ils sont généralement utilisés pour représenter des données structurées, et non pour décrire des calculs. Ceux-ci sont parfois appelés langages de balisage , ou plus exactement « langages conteneurs » ou « langages de description de données ».

Voir également

Remarques

Les références

Lectures complémentaires

Liens externes