Calculabilité

La calculabilité est la capacité à résoudre un problème de manière efficace. C'est un sujet clé du domaine de la théorie de la calculabilité en logique mathématique et de la théorie du calcul en informatique . La calculabilité d'un problème est étroitement liée à l'existence d'un algorithme pour résoudre le problème.

Les modèles de calculabilité les plus étudiés sont les fonctions calculables de Turing et les fonctions μ-récursives , ainsi que le calcul lambda , qui ont tous une puissance de calcul équivalente. D'autres formes de calculabilité sont également étudiées : les notions de calculabilité plus faibles que les machines de Turing sont étudiées dans la théorie des automates , tandis que les notions de calculabilité plus fortes que les machines de Turing sont étudiées dans le domaine de l'hypercalcul .

Une idée centrale de la calculabilité est celle d’un problème ( informatique ) , qui est une tâche dont la calculabilité peut être explorée.

Il existe deux principaux types de problèmes :

• Un problème de décision fixe un ensemble S , qui peut être un ensemble de chaînes, de nombres naturels ou d'autres objets pris dans un ensemble plus grand U . Une instance particulière du problème consiste à décider, étant donné un élément u de U , si u est dans S . Par exemple, soit U l'ensemble des nombres naturels et S l'ensemble des nombres premiers. Le problème de décision correspondant correspond au test de primalité .
• Un problème de fonction consiste à calculer une fonction f d'un ensemble U vers un ensemble V . Une instance du problème consiste à calculer, étant donné un élément u dans U , l'élément correspondant f ( u ) dans V . Par exemple, U et V peuvent être l'ensemble de toutes les chaînes binaires finies, et f peut prendre une chaîne et renvoyer la chaîne obtenue en inversant les chiffres de l'entrée (donc f(0101) = 1010).

D’autres types de problèmes incluent les problèmes de recherche et les problèmes d’optimisation .

L’un des objectifs de la théorie de la calculabilité est de déterminer quels problèmes, ou classes de problèmes, peuvent être résolus dans chaque modèle de calcul.

Un modèle de calcul est une description formelle d'un type particulier de processus de calcul. La description prend souvent la forme d'une machine abstraite destinée à effectuer la tâche à accomplir. Les modèles généraux de calcul équivalents à une machine de Turing (voir la thèse de Church-Turing ) comprennent :

Calcul lambda

Un calcul se compose d'une expression lambda initiale (ou deux si vous souhaitez 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 bêta .

Logique combinatoire

Concept qui présente de nombreuses similitudes avec le -calcul, mais qui présente également des différences importantes (par exemple, le combinateur à point fixe Y a une forme normale en logique combinatoire mais pas en -calcul). La logique combinatoire a été 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 μ-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 f ( x ) les fonctions g ( x ) et h ( x , y ) 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 découler des entrées ci-dessus en utilisant la composition , la récursivité primitive ou la μ-récursivité . Par exemple, si f ( x ) = h ( x , g ( x )) , alors pour que f (5) = 3 apparaisse, des termes comme g (5) = 6 et h (5,6) = 3 doivent apparaître ci-dessus. Le calcul se termine uniquement si le terme final donne la valeur de la fonction récursive appliquée aux entrées.

Systèmes de réécriture de chaînes

Inclut les algorithmes de Markov , qui utilisent des règles de type grammatical pour opérer sur des chaînes de symboles ; également le système post-canonique .

Machine d'enregistrement

Une idéalisation théorique d'un ordinateur. Il existe plusieurs variantes. Dans la plupart d'entre elles, chaque registre peut contenir un nombre naturel (de taille illimitée), et les instructions sont simples (et peu nombreuses), par exemple seules existent la décrémentation (combinée avec un saut conditionnel) et l'incrémentation (et l'arrêt). L'absence de mémoire externe infinie (ou à croissance dynamique) (observée dans les machines de Turing) peut être comprise en remplaçant son rôle par des techniques de numération de Gödel : le fait que chaque registre contienne un nombre naturel permet la possibilité de représenter une chose compliquée (par exemple une séquence, ou une matrice, etc.) par un nombre naturel énorme approprié — l'absence d'ambiguïté de la représentation et de l'interprétation peut être établie par les fondements théoriques des nombres de ces techniques.

Machine de Turing

Également similaire à la machine à états finis, sauf que l'entrée est fournie sur une « bande » d'exécution, sur laquelle la machine de Turing peut lire, écrire ou se déplacer d'avant en arrière au-delà de sa « tête » de lecture/écriture. La bande peut atteindre une taille arbitraire. La machine de Turing est capable d'effectuer des calculs complexes qui peuvent avoir une durée arbitraire. Ce modèle est peut-être le modèle de calcul le plus important en informatique, car il simule le calcul en l'absence de limites de ressources prédéfinies.

Machine de Turing à bandes multiples

Il peut y avoir ici plus d'une bande ; de plus, il peut y avoir plusieurs têtes par bande. Étonnamment, tout calcul pouvant être effectué par ce type de machine peut également être effectué par une machine de Turing ordinaire, bien que cette dernière puisse être plus lente ou nécessiter une plus grande zone totale de sa bande.

P′′

Comme les machines de Turing, P′′ utilise une bande infinie de symboles (sans accès aléatoire) et un ensemble d’instructions plutôt minimaliste. Mais ces instructions sont très différentes, ainsi, contrairement aux machines de Turing, P′′ n’a pas besoin de maintenir un état distinct, car toutes les fonctionnalités « de type mémoire » ne peuvent être fournies que par la bande. Au lieu de réécrire le symbole courant, il peut effectuer une incrémentation arithmétique modulaire sur celui-ci. P′′ dispose également d’une paire d’instructions pour un cycle, inspectant le symbole vide. Malgré sa nature minimaliste, il est devenu le langage formel parental d’un langage de programmation implémenté et (pour le divertissement) utilisé appelé Brainfuck .

Outre les modèles de calcul généraux, certains modèles de calcul 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înes dans de nombreux contextes, des logiciels de productivité bureautique aux langages de programmation . 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 à pile non déterministes sont un autre formalisme équivalent aux grammaires sans contexte.

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 de calcul est d'étudier la classe de langages formels que le modèle peut générer ; on obtient ainsi la hiérarchie des langages de Chomsky .

D’autres modèles restreints de calcul incluent :

Automate fini déterministe (DFA)

Également appelée machine à états finis. Tous les dispositifs informatiques réels existants aujourd'hui peuvent être modélisés comme une machine à états finis, car tous les ordinateurs réels fonctionnent avec des ressources finies. Une telle machine possède un ensemble d'états et un ensemble de transitions d'état qui sont affectées par le flux d'entrée. Certains états sont définis comme étant des états d'acceptation. Un flux d'entrée est introduit dans la machine un caractère à la fois, et les transitions d'état pour l'état actuel sont comparées au flux d'entrée, et s'il existe une transition correspondante, la machine peut entrer dans un nouvel état. Si à la fin du flux d'entrée, la machine est dans un état d'acceptation, alors l'ensemble du flux d'entrée est accepté.

Automate fini non déterministe (NFA)

Un autre modèle simple de calcul, bien que sa séquence de traitement ne soit pas déterminée de manière unique. Il peut être interprété comme empruntant plusieurs chemins de calcul simultanément à travers un nombre fini d'états. Cependant, il est possible de prouver que tout NFA est réductible à un DFA équivalent.

Automate à poussée

Similaire à la machine à états finis, sauf qu'elle dispose d'une pile d'exécution, qui peut croître jusqu'à une taille arbitraire. Les transitions d'état spécifient en outre s'il faut ajouter un symbole à la pile ou en supprimer un. Elle est plus puissante qu'une DFA en raison de sa pile à mémoire infinie, bien que seul l'élément supérieur de la pile soit accessible à tout moment.

Grâce à ces modèles informatiques, nous pouvons déterminer quelles sont leurs limites, c'est-à-dire quelles classes de langages peuvent-ils accepter ?

Les informaticiens appellent langage régulier tout langage pouvant être accepté par une machine à états finis. En raison de la restriction selon laquelle le nombre d'états possibles dans une machine à états finis est fini, nous pouvons voir que pour trouver un langage qui n'est pas régulier, nous devons construire un langage qui nécessiterait un nombre infini d'états.

Un exemple d'un tel langage est l'ensemble de toutes les chaînes constituées des lettres « a » et « b » qui contiennent un nombre égal de lettres « a » et « b ». Pour comprendre pourquoi ce langage ne peut pas être correctement reconnu par une machine à états finis, supposons d'abord qu'une telle machine M existe. M doit avoir un certain nombre d'états n . Considérons maintenant la chaîne x composée de « a » suivis de « b ».

Comme M lit x , il doit y avoir un état dans la machine qui est répété pendant qu'elle lit la première série de 'a', car il y a des 'a' et seulement n états selon le principe du casier . Appelons cet état S , et soit en outre d le nombre de 'a' que notre machine lit afin de passer de la première occurrence de S à une occurrence ultérieure pendant la séquence 'a'. Nous savons donc qu'à cette deuxième occurrence de S , nous pouvons ajouter d (où ) 'a' supplémentaires et nous serons de nouveau à l'état S . Cela signifie que nous savons qu'une chaîne de 'a' doit finir dans le même état que la chaîne de 'a'. Cela implique que si notre machine accepte x , elle doit également accepter la chaîne de 'a' suivie de 'b', ce qui n'est pas dans le langage des chaînes contenant un nombre égal de 'a' et de 'b'. En d’autres termes, M ne peut pas faire correctement la distinction entre une chaîne contenant un nombre égal de « a » et de « b » et une chaîne contenant des « a » et des « b ». $0d>0$0}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cddf6cd1242e088b641c76c3ee375466354f8d5a">

Nous savons donc que ce langage ne peut être accepté correctement par aucune machine à états finis, et n'est donc pas un langage régulier. Une forme plus générale de ce résultat est appelée lemme de pompage pour les langages réguliers , qui peut être utilisé pour montrer que de larges classes de langages ne peuvent pas être reconnues par une machine à états finis.

Les informaticiens définissent un langage qui peut être accepté par un automate à pile comme un langage sans contexte , qui peut être spécifié comme une grammaire sans contexte . Le langage composé de chaînes avec un nombre égal de « a » et de « b », dont nous avons montré qu'il n'était pas un langage régulier, peut être décidé par un automate à pile. De plus, en général, un automate à pile peut se comporter comme une machine à états finis, il peut donc décider de n'importe quel langage régulier. Ce modèle de calcul est donc strictement plus puissant que les machines à états finis.

Cependant, il s'avère qu'il existe des langages qui ne peuvent pas non plus être décidés par un automate à pile. Le résultat est similaire à celui des expressions régulières et ne sera pas détaillé ici. Il existe un lemme de pompage pour les langages sans contexte . Un exemple d'un tel langage est l'ensemble des nombres premiers.

Les machines de Turing peuvent décider n'importe quel langage sans contexte, en plus des langages non décidables par un automate à pile, comme le langage constitué de nombres premiers. Il s'agit donc d'un modèle de calcul strictement plus puissant.

Comme les machines de Turing ont la capacité de « sauvegarder » dans leur bande d'entrée, il est possible pour une machine de Turing de fonctionner pendant une longue période d'une manière qui n'est pas possible avec les autres modèles de calcul décrits précédemment. Il est possible de construire une machine de Turing qui ne finira jamais de fonctionner (s'arrêtera) sur certaines entrées. Nous disons qu'une machine de Turing peut décider d'un langage si elle finira par s'arrêter sur toutes les entrées et donnera une réponse. Un langage qui peut être ainsi décidé est appelé un langage récursif . Nous pouvons décrire plus en détail les machines de Turing qui finiront par s'arrêter et donneront une réponse pour toute entrée dans un langage, mais qui peuvent fonctionner indéfiniment pour les chaînes d'entrée qui ne sont pas dans le langage. De telles machines de Turing pourraient nous dire qu'une chaîne donnée est dans le langage, mais nous ne pouvons jamais être sûrs, en fonction de son comportement, qu'une chaîne donnée n'est pas dans un langage, car elle peut fonctionner indéfiniment dans un tel cas. Un langage qui est accepté par une telle machine de Turing est appelé un langage récursivement énumérable .

Il s’avère que la machine de Turing est un modèle d’automates extrêmement puissant. Les tentatives visant à modifier la définition d’une machine de Turing pour produire une machine plus puissante ont étonnamment échoué. Par exemple, l’ajout d’une bande supplémentaire à la machine de Turing, lui donnant une surface infinie à deux dimensions (ou à trois dimensions ou à n’importe quelle dimension) avec laquelle travailler peuvent tous être simulés par une machine de Turing avec la bande unidimensionnelle de base. Ces modèles ne sont donc pas plus puissants. En fait, une conséquence de la thèse de Church-Turing est qu’il n’existe aucun modèle raisonnable de calcul qui puisse décider de langages qui ne peuvent pas être décidés par une machine de Turing.

La question qui se pose alors est la suivante : existe-t-il des langages qui sont récursivement énumérables, mais pas récursifs ? Et, de plus, existe-t-il des langages qui ne sont même pas récursivement énumérables ?

Le problème de l'arrêt est l'un des problèmes les plus connus de l'informatique, car il a de profondes implications sur la théorie de la calculabilité et sur la façon dont nous utilisons les ordinateurs dans la pratique quotidienne. Le problème peut être formulé ainsi :

Étant donné une description d'une machine de Turing et de son entrée initiale, déterminez si le programme, lorsqu'il est exécuté sur cette entrée, s'arrête (se termine). L'alternative est qu'il s'exécute indéfiniment sans s'arrêter.

Ici, nous ne posons pas une simple question sur un nombre premier ou un palindrome, mais nous renversons la situation et demandons à une machine de Turing de répondre à une question sur une autre machine de Turing. On peut montrer (voir l'article principal : Problème de l'arrêt ) qu'il n'est pas possible de construire une machine de Turing capable de répondre à cette question dans tous les cas.

Autrement dit, la seule façon générale de savoir avec certitude si un programme donné s'arrêtera sur une entrée particulière dans tous les cas est simplement de l'exécuter et de voir s'il s'arrête. S'il s'arrête, alors vous savez qu'il s'arrête. S'il ne s'arrête pas, cependant, vous ne pouvez jamais savoir s'il finira par s'arrêter. Le langage constitué de toutes les descriptions de machines de Turing associées à tous les flux d'entrée possibles sur lesquels ces machines de Turing finiront par s'arrêter, n'est pas récursif. Le problème de l'arrêt est donc appelé non-calculable ou indécidable .

Une extension du problème d'arrêt est appelée théorème de Rice , qui stipule qu'il est indécidable (en général) qu'un langage donné possède une propriété non triviale spécifique.

Le problème de l'arrêt est cependant facile à résoudre si nous admettons que la machine de Turing qui décide de s'arrêter peut fonctionner indéfiniment lorsqu'on lui donne en entrée une représentation d'une machine de Turing qui ne s'arrête pas elle-même. Le langage qui s'arrête est donc récursivement énumérable. Il est cependant possible de construire des langages qui ne sont même pas récursivement énumérables.

Un exemple simple d'un tel langage est le complément du langage d'arrêt ; c'est-à-dire le langage constitué de toutes les machines de Turing appariées avec des chaînes d'entrée où les machines de Turing ne s'arrêtent pas sur leur entrée. Pour voir que ce langage n'est pas récursivement énumérable, imaginons que nous construisions une machine de Turing M qui soit capable de donner une réponse définie pour toutes ces machines de Turing, mais qu'elle puisse fonctionner indéfiniment sur toute machine de Turing qui s'arrête finalement. Nous pouvons alors construire une autre machine de Turing qui simule le fonctionnement de cette machine, tout en simulant directement l'exécution de la machine donnée en entrée également, en entrelaçant l'exécution des deux programmes. Puisque la simulation directe finira par s'arrêter si le programme qu'elle simule s'arrête, et puisque par hypothèse la simulation de M finira par s'arrêter si le programme d'entrée ne s'arrête jamais, nous savons que finira par avoir une de ses versions parallèles s'arrêter. est donc un décideur pour le problème d'arrêt. Nous avons cependant montré précédemment que le problème d'arrêt est indécidable. Nous avons une contradiction, et nous avons ainsi montré que notre hypothèse selon laquelle M existe est incorrecte. Le complément du langage discontinu n'est donc pas récursivement énumérable.

Plusieurs modèles de calcul basés sur la concurrence ont été développés, notamment la machine à accès aléatoire parallèle et le réseau de Petri . Ces modèles de calcul concurrent n'implémentent toujours aucune fonction mathématique qui ne puisse pas être implémentée par les machines de Turing.

La thèse de Church-Turing suppose qu'il n'existe aucun modèle de calcul efficace capable de calculer plus de fonctions mathématiques qu'une machine de Turing. Les informaticiens ont imaginé de nombreuses variétés d' hypercalculateurs , des modèles de calcul qui vont au-delà de la calculabilité de Turing.

Imaginez une machine où chaque étape du calcul nécessite la moitié du temps de l'étape précédente (et espérons-le la moitié de l'énergie de l'étape précédente...). Si nous normalisons à 1/2 unité de temps la quantité de temps nécessaire à la première étape (et à 1/2 unité d'énergie la quantité d'énergie nécessaire à la première étape...), l'exécution nécessiterait

unité de temps (et 1 unité d'énergie...) à exécuter. Cette série infinie converge vers 1, ce qui signifie que cette machine Zeno peut exécuter un nombre dénombrable infini d'étapes en 1 unité de temps (en utilisant 1 unité d'énergie...). Cette machine est capable de résoudre le problème d'arrêt en simulant directement l'exécution de la machine en question. Par extension, toute série infinie convergente [doit être prouvée infinie] fonctionnerait. En supposant que la série infinie converge vers une valeur n , la machine Zeno terminerait une exécution dénombrable infinie en n unités de temps.

Les machines dites Oracle ont accès à divers « oracles » qui fournissent la solution à des problèmes spécifiques indécidables. Par exemple, la machine de Turing peut avoir un « oracle d'arrêt » qui répond immédiatement si une machine de Turing donnée s'arrêtera un jour sur une entrée donnée. Ces machines sont un sujet d'étude central en théorie de la récursivité .

Même ces machines, qui semblent représenter la limite des automates que nous pourrions imaginer, rencontrent leurs propres limites. Si chacune d’entre elles peut résoudre le problème d’arrêt d’une machine de Turing, elles ne peuvent pas résoudre leur propre version du problème d’arrêt. Par exemple, une machine Oracle ne peut pas répondre à la question de savoir si une machine Oracle donnée s’arrêtera un jour.