Théorie du calcul - Theory of computation

Une représentation artistique d'une machine de Turing . Les machines de Turing sont fréquemment utilisées comme modèles théoriques pour le calcul.

En informatique théorique et en mathématiques , la théorie du calcul est la branche qui traite des problèmes qui peuvent être résolus sur un modèle de calcul , à l'aide d'un algorithme , de l' efficacité avec laquelle ils peuvent être résolus ou à quel degré (par exemple, des solutions approximatives par rapport à des solutions précises ). Le domaine est divisé en trois branches principales : la théorie des automates et les langages formels , la théorie de la calculabilité et la théorie de la complexité computationnelle , qui sont liées par la question : "Quelles sont les capacités et limitations fondamentales des ordinateurs ?".

Afin d'effectuer une étude rigoureuse du calcul, les informaticiens travaillent avec une abstraction mathématique des ordinateurs appelée modèle de calcul . Il existe plusieurs modèles en usage, mais le plus couramment examiné est la machine de Turing . Les informaticiens étudient la machine de Turing parce qu'elle est simple à formuler, qu'elle peut être analysée et utilisée pour prouver des résultats, et parce qu'elle représente ce que beaucoup considèrent comme le modèle de calcul « raisonnable » le plus puissant possible (voir la thèse de Church-Turing ). Il peut sembler que la capacité de mémoire potentiellement infinie soit un attribut irréalisable, mais tout problème décidable résolu par une machine de Turing ne nécessitera toujours qu'une quantité finie de mémoire. Donc, en principe, tout problème qui peut être résolu (décidé) par une machine de Turing peut être résolu par un ordinateur qui a une quantité finie de mémoire.

Histoire

La théorie du calcul peut être considérée comme la création de modèles de toutes sortes dans le domaine de l'informatique. Par conséquent, les mathématiques et la logique sont utilisées. Au siècle dernier, elle est devenue une discipline académique indépendante et a été séparée des mathématiques.

Quelques pionniers de la théorie du calcul étaient Ramon Llull , Alonzo Church , Kurt Gödel , Alan Turing , Stephen Kleene , Rózsa Péter , John von Neumann et Claude Shannon .

Branches

Théorie des automates

Grammaire Langues Automate Règles de production (contraintes)
Type-0 Récursivement énumérable Machine de Turing (pas de restrictions)
Type 1 Sensible au contexte Machine de Turing non déterministe bornée linéaire
Type 2 Sans contexte Automate à pile non déterministe
Type-3 Ordinaire Automate à états finis
et

La théorie des automates est l'étude des machines abstraites (ou, de manière plus appropriée, des machines ou systèmes « mathématiques » abstraits) et des problèmes informatiques qui peuvent être résolus à l'aide de ces machines. Ces machines abstraites sont appelées automates. Automata vient du mot grec (Αυτόματα) qui signifie que quelque chose fait quelque chose par lui-même. La théorie des automates est également étroitement liée à la théorie des langages formels , car les automates sont souvent classés par classe de langages formels qu'ils sont capables de reconnaître. Un automate peut être une représentation finie d'un langage formel qui peut être un ensemble infini. Les automates sont utilisés comme modèles théoriques pour les machines informatiques et sont utilisés pour des preuves de calculabilité.

Théorie du langage formel

La hiérarchie de Chomsky
Ensemble des inclusions décrites par la hiérarchie de Chomsky

La théorie des langues est une branche des mathématiques qui s'intéresse à la description des langues comme un ensemble d'opérations sur un alphabet . Elle est étroitement liée à la théorie des automates, car les automates sont utilisés pour générer et reconnaître des langages formels. Il existe plusieurs classes de langages formels, chacun permettant une spécification de langage plus complexe que le précédent, c'est-à-dire la hiérarchie de Chomsky , et correspondant chacun à une classe d'automates qui le reconnaît. Parce que les automates sont utilisés comme modèles de calcul, les langages formels sont le mode de spécification préféré pour tout problème qui doit être calculé.

Théorie de la calculabilité

La théorie de la calculabilité traite principalement de la question de savoir dans quelle mesure un problème peut être résolu sur un ordinateur. L'affirmation selon laquelle le problème d'arrêt ne peut pas être résolu par une machine de Turing est l'un des résultats les plus importants de la théorie de la calculabilité, car c'est un exemple de problème concret qui est à la fois facile à formuler et impossible à résoudre à l'aide d'une machine de Turing. Une grande partie de la théorie de la calculabilité s'appuie sur le résultat du problème hésitant.

Une autre étape importante dans la théorie de la calculabilité était le théorème de Rice , qui stipule que pour toutes les propriétés non triviales des fonctions partielles, il est indécidable si une machine de Turing calcule une fonction partielle avec cette propriété.

La théorie de la calculabilité est étroitement liée à la branche de la logique mathématique appelée théorie de la récursivité , qui supprime la restriction d'étudier uniquement les modèles de calcul qui sont réductibles au modèle de Turing. De nombreux mathématiciens et théoriciens du calcul qui étudient la théorie de la récursivité l'appelleront théorie de la calculabilité.

Théorie de la complexité computationnelle

Une représentation de la relation entre les classes de complexité

La théorie de la complexité considère non seulement si un problème peut être résolu sur un ordinateur, mais aussi avec quelle efficacité le problème peut être résolu. Deux aspects majeurs sont considérés : la complexité temporelle et la complexité spatiale, qui sont respectivement le nombre d'étapes nécessaires pour effectuer un calcul, et la quantité de mémoire nécessaire pour effectuer ce calcul.

Afin d'analyser le temps et l'espace requis par un algorithme donné , les informaticiens expriment le temps ou l'espace requis pour résoudre le problème en fonction de la taille du problème d'entrée. Par exemple, trouver un nombre particulier dans une longue liste de nombres devient plus difficile à mesure que la liste de nombres s'allonge. Si nous disons qu'il y a n nombres dans la liste, alors si la liste n'est pas triée ou indexée de quelque manière que ce soit, nous devrons peut-être regarder chaque nombre afin de trouver le nombre que nous recherchons. On dit donc que pour résoudre ce problème, l'ordinateur doit effectuer un certain nombre d'étapes qui croissent linéairement dans la taille du problème.

Pour simplifier ce problème, les informaticiens ont adopté la notation Big O , qui permet de comparer les fonctions d'une manière qui garantit que des aspects particuliers de la construction d'une machine n'ont pas besoin d'être pris en compte, mais uniquement le comportement asymptotique lorsque les problèmes deviennent importants. Ainsi, dans notre exemple précédent, nous pourrions dire que le problème nécessite des étapes pour être résolu.

Le problème ouvert le plus important de toute l' informatique est peut-être la question de savoir si une certaine grande classe de problèmes notés NP peut être résolue efficacement. Ceci est discuté plus en détail dans les classes de complexité P et NP , et le problème P contre NP est l'un des sept problèmes du prix du millénaire énoncés par le Clay Mathematics Institute en 2000. La description officielle du problème a été donnée par le lauréat du prix Turing, Stephen Cook .

Modèles de calcul

En dehors d'une machine de Turing , d'autres modèles de calcul équivalents (voir : Church-Turing thesis ) sont utilisés.

Calcul lambda
Un calcul consiste en une expression lambda initiale (ou deux si vous voulez séparer la fonction et son entrée) plus une séquence finie de termes lambda, chacun déduit du terme précédent par une application de réduction Beta .
Logique combinatoire
est un concept qui présente de nombreuses similitudes avec le -calcul, mais il existe également des différences importantes (par exemple, le combinateur à virgule fixe Y a une forme normale en logique combinatoire mais pas en -calcul). La logique combinatoire s'est développée avec de grandes ambitions : comprendre la nature des paradoxes, rendre les fondements des mathématiques plus économiques (conceptuellement), éliminer la notion de variables (clarifiant ainsi leur rôle en mathématiques).
fonctions μ-récursives
un calcul consiste en une fonction mu-récursive, c'est -à- dire sa séquence de définition, toute valeur d'entrée et une séquence de fonctions récursives apparaissant dans la séquence de définition avec des entrées et des sorties. Ainsi, si dans la séquence de définition d'une fonction récursive les fonctions et apparaissent, alors des termes de la forme 'g(5)=7' ou 'h(3,2)=10' peuvent apparaître. Chaque entrée de cette séquence doit être une application d'une fonction de base ou suivre les entrées ci-dessus en utilisant la composition , la récursivité primitive ou la récursivité . Par exemple, si , alors pour que 'f(5)=3' apparaisse, des termes comme 'g(5)=6' et 'h(5,6)=3' doivent apparaître au-dessus. Le calcul ne se termine que si le terme final donne la valeur de la fonction récursive appliquée aux entrées.
Algorithme de Markov
un système de réécriture de chaînes qui utilise des règles de type grammaire pour opérer sur des chaînes de symboles.
Enregistrer la machine
est une idéalisation théoriquement intéressante d'un ordinateur. Il existe plusieurs variantes. Dans la plupart d'entre eux, chaque registre peut contenir un nombre naturel (de taille illimitée), et les instructions sont simples (et peu nombreuses), par exemple seules la décrémentation (combinée à un saut conditionnel) et l'incrémentation existent (et s'arrêtent). L'absence de la mémoire externe infinie (ou en croissance dynamique) (observée sur les machines de Turing) peut être comprise en remplaçant son rôle par les techniques de numérotation de Gödel : le fait que chaque registre contienne un nombre naturel permet de représenter une chose compliquée (par exemple un séquence, ou une matrice, etc.) par un grand nombre naturel approprié - l'absence d'ambiguïté à la fois de la représentation et de l'interprétation peut être établie par les fondements théoriques des nombres de ces techniques.

En plus des modèles informatiques généraux, certains modèles informatiques plus simples sont utiles pour des applications spéciales et restreintes. Les expressions régulières , par exemple, spécifient des modèles de chaîne dans de nombreux contextes, des logiciels de productivité bureautique aux langages de programmation . Un autre formalisme mathématiquement équivalent aux expressions régulières, les automates finis sont utilisés dans la conception de circuits et dans certains types de résolution de problèmes. Les grammaires sans contexte spécifient la syntaxe du langage de programmation. Les automates à refoulement non déterministes sont un autre formalisme équivalent aux grammaires sans contexte. Les fonctions récursives primitives sont une sous-classe définie des fonctions récursives.

Différents modèles de calcul ont la capacité d'effectuer différentes tâches. Une façon de mesurer la puissance d'un modèle informatique consiste à étudier la classe de langages formels que le modèle peut générer ; on obtient ainsi la hiérarchie de Chomsky des langues.

Les références

Lectures complémentaires

Manuels destinés aux informaticiens

(Il existe de nombreux manuels dans ce domaine ; cette liste est nécessairement incomplète.)

Livres sur la théorie de la calculabilité du point de vue mathématique (plus large)
Perspective historique

Liens externes