Une introduction à la théorie de la calculabilité et à la complexité

Vous êtes-vous déjà demandé : quel est exactement l'appareil sur lequel vous lisez cet article ? Qu'est-ce qu'un ordinateur?

La science informatique remonte à une époque bien avant que ces appareils informatiques modernes ne soient même imaginés. Dans une industrie où les questions les plus fréquemment posées tournent autour des langages de programmation, des frameworks et des bibliothèques, nous tenons souvent pour acquis les concepts fondamentaux qui font fonctionner un ordinateur.

Mais ces ordinateurs, qui semblent posséder un potentiel infini, ont-ils des limites ? Y a-t-il des problèmes que les ordinateurs ne peuvent pas résoudre ?

Dans cet article, nous aborderons ces questions en nous éloignant des particularités des langages de programmation et des architectures informatiques. En comprenant la puissance et les limites des ordinateurs et des algorithmes, nous pouvons améliorer notre façon de penser et mieux raisonner sur différentes stratégies.

La vision abstraite de l'informatique produit des résultats qui ont résisté à l'épreuve du temps, étant aussi précieux pour nous aujourd'hui qu'ils l'étaient lors de leur développement initial dans les années 1970.

Calculabilité

Qu'est-ce qu'un ordinateur? Qu'est-ce qu'un problème ?

À l'école, on nous enseigne souvent un modèle mental de problèmes et de fonctions qui ressemble à ceci :

Une fonction est une procédure que vous appliquez à une entrée x afin de trouver une sortie f(x).

Il s'avère que la définition mathématique est différente :

Une fonction est un ensemble de paires ordonnées telles que le premier élément de chaque paire provient d'un ensemble X (appelé domaine), le deuxième élément de chaque paire provient d'un ensemble Y (appelé codomaine ou intervalle), et chaque élément de le domaine est apparié avec exactement un élément de la gamme.

C'était tout à fait la bouchée. Mais qu'est ce que ca signifie exactement?

Cette définition nous dit qu'un ordinateur est une machine pour calculer des fonctions.

Pourquoi?

Parce que les ordinateurs transforment une entrée arbitraire en une sortie. En d'autres termes, ils résolvent des problèmes. Les deux définitions des fonctions, celle qui nous est si familière et celle formelle, coïncident à de nombreuses fins pratiques.

Cependant, la définition mathématique nous permet de tirer des conclusions intéressantes telles que l'existence de fonctions non calculables (c'est-à-dire de problèmes insolubles) :

Parce que toutes les fonctions ne peuvent pas être décrites comme un algorithme.

Règles du jeu

Pour nous aider à faire valoir nos arguments, imaginons les ordinateurs comme des machines prenant des entrées, effectuant une séquence d'opérations et, après un certain temps, donnant des sorties.

Nous appellerons l'entrée l'alphabet de la machine ; c'est-à-dire un ensemble de chaînes de caractères d'un ensemble fini. Par exemple, l'alphabet de la machine peut être binaire (0 et 1) ou il peut s'agir du jeu de caractères ASCII. Toute séquence finie de caractères est une chaîne, par exemple, "0110".

De plus, nous représenterons la sortie d'une machine comme une décision binaire d'acceptation-rejet, délivrée une fois que la machine aura (espérons-le) terminé son calcul. Cette abstraction correspond bien à la définition mathématique des fonctions de plus tôt.

Compte tenu de ces paramètres, il est important de caractériser un autre type : une collection de chaînes. Peut-être que nous nous soucions de l'ensemble de chaînes qu'une machine accepte, ou peut-être que nous construisons une machine qui accepte des chaînes dans un certain ensemble et pas d'autres, ou peut-être que nous demandons s'il est même possible de concevoir une machine qui accepte tout dans certains ensemble particulier et pas d'autres.

Dans tous ces cas, un ensemble de chaînes est appelé un langage, par exemple, l'ensemble de toutes les chaînes binaires qui représentent des nombres pairs ou l'ensemble des chaînes qui ont un nombre pair de caractères. Il s'avère que les langages, comme les nombres, peuvent être exploités avec des opérateurs tels que la concaténation, l'union, l'intersection, etc.

Un opérateur important est l'opérateur étoile de Kleene qui est également utilisé avec les expressions régulières. Cela peut être considéré comme l'union de tous les pouvoirs possibles de la langue. Par exemple, si notre langage A est l'ensemble de chaînes { '01', '1' }, alors un membre de A* est la chaîne '0101111'.

Comptabilité

La dernière pièce du puzzle avant de prouver notre affirmation selon laquelle toutes les fonctions ne sont pas calculables est le concept de dénombrabilité. Intuitivement, notre preuve montrera qu'il y a plus de langues ; c'est-à-dire plus de problèmes qu'il n'y a de programmes possibles pour les résoudre. Cela fonctionne parce que la question de savoir si une chaîne appartient à une langue (Oui/Non) est elle-même un problème.

Plus précisément, notre preuve affirme que l'ensemble des programmes possibles est infiniment dénombrable tandis que l'ensemble des langues sur un alphabet est infiniment infini.

À ce stade, vous pensez peut-être : « L'infini est une idée assez étrange en soi ; maintenant je dois m'occuper de deux d'entre eux !

Eh bien, ce n'est pas si mal. Un ensemble dénombrable infini est un ensemble qui peut être énuméré. Il est possible de dire ceci est le premier élément, ceci est le deuxième élément, et ainsi de suite, en attribuant éventuellement un numéro à chaque élément de l'ensemble. Prenons l'ensemble des nombres pairs, par exemple. On peut dire que 2 est le premier, 4 le deuxième, 6 le troisième, et ainsi de suite. De tels ensembles sont dénombrables infinis ou dénombrables.

Avec certains ensembles cependant, comme les vrais nombres, peu importe à quel point vous êtes intelligent ; il n'y a tout simplement pas d'énumération. Ces ensembles sont indénombrables infinis ou indénombrables.

D'innombrables programmes

Premièrement, nous voulons montrer que l'ensemble des programmes informatiques est dénombrable. Pour nos besoins, nous le faisons en observant que l'ensemble de toutes les chaînes sur un alphabet fini est dénombrable. Cela fonctionne parce que les programmes informatiques sont eux-mêmes des chaînes finies.

La preuve est simple et nous ne couvrons pas les détails ici. L'essentiel est qu'il existe autant de programmes informatiques qu'il existe, disons, de nombres naturels.

Recommencer:

L'ensemble de toutes les chaînes sur n'importe quel alphabet (par exemple, l'ensemble de tous les programmes informatiques) est dénombrable.

Un nombre incalculable de langues

Compte tenu de cette conclusion, qu'en est-il des sous-ensembles de ces chaînes ? Autrement dit, qu'en est-il de l'ensemble de toutes les langues ? Il s'avère que cet ensemble est indénombrable.

L'ensemble de toutes les langues sur n'importe quel alphabet est indénombrable.

Encore une fois, nous ne couvrons pas la preuve ici.

Conséquences

Bien qu'elles ne soient pas immédiatement apparentes, les conséquences de l'indénombrabilité des langages et de la dénombrabilité de l'ensemble de tous les programmes informatiques sont profondes.

Pourquoi?

Supposons que A soit le jeu de caractères ASCII ; Les caractères ASCII ne sont que ceux nécessaires pour composer un programme informatique. Nous pouvons voir que l'ensemble des chaînes qui représentent, disons, les programmes JavaScript, est un sous-ensemble de A* (ici, * est l'opérateur étoile de Kleene). Le choix de JavaScript est arbitraire. Puisque cet ensemble de programmes est un sous-ensemble d'un ensemble dénombrable, nous avons que l'ensemble des programmes JavaScript est dénombrable.

De plus, considérons que pour tout langage L , nous pouvons définir une fonction f qui vaut 1 si une chaîne x est dans L et 0 sinon. Toutes ces fonctions sont distinctes. Parce qu'il y a une correspondance 1: 1 avec l'ensemble de toutes les langues et parce que l'ensemble de toutes les langues est indénombrable, nous avons que l'ensemble de toutes ces fonctions est indénombrable.

Voici le point profond :

Étant donné que l'ensemble de tous les programmes valides est dénombrable mais que l'ensemble des fonctions ne l'est pas, il doit y avoir certaines fonctions pour lesquelles nous ne pouvons tout simplement pas écrire de programmes.

Nous ne savons pas encore à quoi ressemblent ces fonctions ou ces problèmes, mais nous savons qu'ils existent. C'est une leçon d'humilité, car il y a des problèmes pour lesquels il n'y a pas de solution. Nous considérons que les ordinateurs sont extrêmement puissants et capables, mais certaines choses sont même hors de leur portée.

Maintenant, la question devient : « À quoi ressemblent ces problèmes ? Avant de continuer à décrire de tels problèmes, nous devons d'abord modéliser le calcul de manière généralisée.

Machines de Turing

L'un des tout premiers modèles mathématiques d'un ordinateur a été développé par Alan Turing. Ce modèle, appelé la machine de Turing, est un dispositif extrêmement simple qui capture complètement notre notion de calculabilité.

L'entrée de la machine est une bande sur laquelle l'entrée a été écrite. À l'aide d'une tête de lecture/écriture, la machine transforme l'entrée en sortie via une série d'étapes. À chaque étape, une décision est prise quant à savoir si et quoi écrire sur la bande et s'il faut la déplacer vers la droite ou vers la gauche. Cette décision est basée sur exactement deux choses :

• Le symbole actuel sous la tête, et

• L'état interne de la machine, qui est également mis à jour au fur et à mesure que le symbole est écrit

C'est ça.

Universalité

En 1926, Alan Turing a non seulement développé la machine de Turing, mais a également eu un certain nombre d'autres idées majeures sur la nature du calcul lorsqu'il a écrit son célèbre article, "On Computable Numbers". Il s'est rendu compte qu'un programme informatique lui-même pouvait être considéré comme une entrée dans un ordinateur. De ce point de vue, il a eu la belle idée qu'une machine de Turing puisse simuler ou exécuter cette entrée.

Alors que nous tenons ces idées pour acquises aujourd'hui, à l'époque de Turing, l'idée d'une telle machine universelle a été la percée majeure qui a permis à Turing de développer des problèmes insolubles.

Thèse de Church-Turing

Avant de continuer, examinons un point important : nous savons que la machine de Turing est un modèle de calcul, mais est-elle suffisamment générale ? Pour répondre à cette question, nous nous tournons vers la thèse de Church-Turing, qui donne foi à la déclaration suivante :

Tout ce qui est calculable est calculable par une machine de Turing.

Alors que Turing a développé la machine de Turing comme modèle de calcul, Alonzo Church a également développé un modèle de calcul connu sous le nom de lambda-calcul. Ces modèles sont puissants, car ils décrivent tous les deux le calcul et le font d'une manière égale à n'importe lequel des ordinateurs d'aujourd'hui ou d'ailleurs à n'importe quel ordinateur. Cela signifie que nous pouvons utiliser une machine de Turing pour décrire les problèmes insolubles que nous recherchons, sachant que nos découvertes s'appliqueraient à tous les ordinateurs possibles passés, présents et au-delà.

Reconnaissabilité et décidabilité

Nous devons couvrir un peu plus de contexte avant de décrire concrètement un problème insoluble, à savoir les concepts de reconnaisseurs de langage et de décideurs de langage.

Un langage est reconnaissable s'il existe une machine de Turing qui le reconnaît.

et

Un langage est décidable s'il existe une machine de Turing qui le décide.

Pour reconnaître un langage, une machine de Turing doit accepter toutes les chaînes du langage et ne doit rien accepter qui ne soit pas dans le langage. Il peut rejeter ou boucler sur de telles chaînes. Pour être décideur, une machine de Turing doit toujours s'arrêter sur son entrée soit en acceptant, soit en rejetant.

Ici, l'idée de s'arrêter à l'entrée est essentielle. En fait, nous voyons que les décideurs sont plus puissants que les reconnaisseurs. De plus, un problème est résoluble, ou en d'autres termes, une fonction n'est décidable que s'il existe une machine de Turing qui décide du langage décrit par la fonction.

Indécidabilité

Si vous avez déjà écrit un programme informatique, vous devez sûrement connaître la sensation d'être assis là à regarder l'ordinateur tourner ses roues lorsque le programme est exécuté. Vous ne savez pas si le programme prend juste beaucoup de temps ou s'il y a une erreur dans le code provoquant une boucle infinie. Vous vous êtes peut-être même demandé pourquoi le compilateur ne vérifie pas le code pour voir s'il s'arrêterait ou bouclerait indéfiniment lors de son exécution.

Le compilateur n'a pas une telle vérification car cela ne peut tout simplement pas être fait. Ce n'est pas que les ingénieurs compilateurs ne sont pas assez intelligents ou manquent de ressources ; il est tout simplement impossible de vérifier un programme informatique arbitraire pour déterminer s'il s'arrête.

Nous pouvons le prouver en utilisant la machine de Turing. Les machines de Turing peuvent être décrites comme des chaînes, il y en a donc un nombre dénombrable. Supposons que M ₁ , M ₂ , etc. constituent l'ensemble de toutes les machines de Turing. Définissons la fonction suivante :

Ici, <M> est la syntaxe du "codage de chaîne de M", et cette fonction représente le problème de la sortie de 1 si M _i s'arrête en acceptant M _j en entrée et de la sortie de 0 sinon. Notez que M _i doit s'arrêter (c'est-à-dire être un décideur). Ceci est nécessaire car nous souhaitons décrire une fonction indécidable (c'est-à-dire un problème insoluble).

Maintenant, définissons également un langage L composé d'encodages de chaînes de machines de Turing qui n'acceptent PAS leurs propres descriptions :

Par exemple, une machine M ₁ peut sortir 0 sur l'entrée <M ₁ > tandis qu'une autre machine M ₂ peut sortir 1 sur l'entrée <M ₂ >. Pour prouver que ce langage est indécidable, nous demandons ce que M _L , la machine qui décide du langage L, fait quand on lui donne sa propre description <M _L > en entrée. Il y a deux possibilités :

M _L accepte <M _L >

ou

M _L rejette <M _L >

Si M _L accepte son propre codage, alors cela signifie que <M _L > n'est pas dans la langue L ; cependant, si tel était le cas, alors M _L n'aurait pas dû accepter son codage en premier lieu. Par contre, si M _L n'accepte pas son propre codage, alors <M _L > est dans le langage L, donc M _L aurait dû accepter son codage de chaîne.

Dans les deux cas, on a un paradoxe, ou en termes mathématiques, une contradiction, prouvant que le langage L est indécidable ; ainsi, nous avons décrit notre premier problème insoluble.

Problème d'arrêt

Bien que le problème que nous venons de décrire puisse ne pas sembler pertinent, il peut être réduit à d'autres problèmes insolubles d'importance pratique, notamment le problème d'arrêt :

Le langage des encodages des machines de Turing qui s'arrêtent sur la chaîne vide.

Le problème d'arrêt s'applique à la question de savoir pourquoi les compilateurs ne peuvent pas détecter les boucles infinies antérieures. Si nous ne pouvons pas déterminer si un programme se termine sur la chaîne vide, alors comment pourrions-nous déterminer si son exécution entraînerait une boucle infinie ?

À ce stade, il peut sembler que nous venons d'agiter nos mains pour parvenir à une conclusion simple; cependant, nous avons réalisé qu'aucune machine de Turing ne peut dire si un programme informatique va s'arrêter ou rester en boucle indéfiniment. C'est un problème important avec les applications pratiques, et il ne peut pas être résolu sur une machine de Turing ou sur tout autre type d'ordinateur. Un iPhone ne peut pas résoudre ce problème. Un bureau avec de nombreux cœurs ne peut pas résoudre ce problème. Le cloud ne peut pas résoudre ce problème. Même si quelqu'un devait inventer un ordinateur quantique, il ne serait toujours pas capable de résoudre le problème de l'arrêt.

Sommaire

Dans notre examen de la théorie de la calculabilité, nous avons vu qu'il existe de nombreuses fonctions qui ne sont calculables dans aucun sens ordinaire du terme par un argument de comptage. Nous avons précisément défini ce que nous entendons par calcul, en remontant jusqu'à l'inspiration de Turing à partir de sa propre expérience avec un stylo et du papier pour formaliser la machine de Turing. Nous avons vu comment ce modèle peut calculer tout ce que n'importe quel ordinateur aujourd'hui ou prévu pour demain peut, et nous avons réalisé une classe de problèmes qui ne sont pas calculables du tout.

Pourtant, la calculabilité a un inconvénient. Ce n'est pas parce que nous pouvons résoudre un problème que nous pouvons le résoudre rapidement. Après tout, à quoi sert un ordinateur si son calcul ne va pas se terminer avant que le soleil ne devienne une nova sur nous des dizaines de millions d'années dans le futur ?

Laissant de côté les fonctions et les langages calculables, nous discutons maintenant de la complexité du calcul, examinant le calcul efficace et le fameux problème P contre NP.

Complexité

Lent vs Rapide

Les informaticiens reconnaissent une variété de classes de problèmes, et deux classes qui nous intéressent comprennent les problèmes que les ordinateurs peuvent résoudre rapidement ou efficacement appelés P et les problèmes dont les solutions peuvent être vérifiées rapidement mais ne peuvent pas être obtenues rapidement appelées NP .

Par exemple, supposons que vous soyez responsable du développement d'algorithmes pour un service de rencontres en ligne et que quelqu'un pose la question : « Tout le monde peut-il avoir un rendez-vous ? » La réponse se résume à jumeler des individus compatibles de sorte que tout le monde soit jumelé. Il s'avère qu'il existe des algorithmes efficaces pour résoudre ce problème. Ce problème est dans l'ensemble P .

Eh bien, et si nous voulions identifier la plus grande clique parmi nos utilisateurs ? Par clique, nous entendons le plus grand réseau d'individus qui sont tous compatibles les uns avec les autres. Lorsque le nombre d'utilisateurs est faible, ce problème peut être résolu rapidement. Nous pouvons facilement identifier, disons, une clique avec 3 utilisateurs. Cependant, à mesure que nous commençons à rechercher des cliques plus importantes, le problème devient de plus en plus difficile à résoudre. Ce problème est dans l'ensemble NP .

Définitions formelles

P est l'ensemble des problèmes résolubles en temps polynomial. Autrement dit, le nombre d'étapes de calcul est limité par une fonction polynomiale par rapport à la taille du problème. Nous savons que le « Tout le monde peut-il avoir un rendez-vous ? » question, également connue sous le nom de problème d'appariement biparti, est dans P .

NP est l'ensemble des problèmes vérifiables en temps polynomial. Cela inclut bien sûr tous les problèmes de P ; cependant, nous ne savons pas si ce confinement est strict. Nous connaissons des problèmes qui sont effectivement vérifiables mais pas efficacement solubles, mais nous ne savons pas si le problème est vraiment insoluble. Le problème de la clique est l'un de ces problèmes. Nous savons que nous pouvons vérifier la solution efficacement, mais nous ne savons pas avec certitude si nous pouvons résoudre le problème efficacement.

Enfin, NP-complet est l'ensemble des problèmes qui sont les problèmes les plus difficiles de NP . Ils sont considérés comme les plus difficiles car tout problème dans NP peut être transformé efficacement en NPC . En conséquence, si quelqu'un devait identifier une solution efficace à un problème dans NPC , alors la classe entière de NP serait absorbée par P . Le problème de la clique est aussi dans NPC .

Ainsi, nous arrivons au problème de P vs. NP . De nombreux informaticiens et mathématiciens croient fermement que P et NP ne sont pas égaux. S'ils l'étaient, les implications seraient plus que profondes. Une grande partie de l'infrastructure numérique d'aujourd'hui repose sur le fait qu'il y a des problèmes dans NP qui ne sont pas dans P . Si ce n'était pas le cas, les méthodes cryptographiques, par exemple, s'effondreraient du jour au lendemain, permettant à une personne possédant une solution efficace à un problème de PNJ de subvertir même les protocoles de sécurité les plus stricts.

Subtilités de traçabilité

Pour les novices en informatique, la différence entre les problèmes d'appariement et de clique peut ne pas sembler un gros problème. En fait, la différence entre un problème en P et un problème en NP peut être très subtile. Être capable de faire la différence est important pour quiconque conçoit des algorithmes dans le monde réel.

Considérons le problème du plus court chemin. Étant donné deux emplacements, l'objectif est d'identifier le chemin le plus court entre eux. Un iPhone calcule cela en quelques millisecondes. Il s'agit d'un problème calculable.

D'autre part, considérons le problème du voyageur de commerce, où l'objectif est de visiter un sous-ensemble de destinations possibles se terminant à l'origine tout en parcourant la distance la plus courte possible. Ce problème est similaire au problème du plus court chemin mais est NP-complet ; cela explique également pourquoi la logistique de la chaîne d'approvisionnement est une industrie d'un milliard de dollars.

Nous pouvons en fait être encore plus subtils. Au lieu de demander le chemin le plus court (P), on peut demander le chemin le plus long sans cycles. Il s'avère que le problème du chemin le plus long est également NP-complet.

Il existe de nombreux autres exemples de cette distinction subtile, notamment l'identification des couvertures de sommets dans les graphes bipartis et généraux ou la satisfaction des formules booléennes avec deux ou trois littéraux par clause. Le fait est qu'il n'est pas immédiatement évident de savoir si un problème est dans P ou NP, et c'est pourquoi l'analyse du temps d'exécution est une compétence essentielle. Si l'algorithme à concevoir est pour un problème en P, alors nous savons qu'il existe une solution efficace. Si, d'autre part, le problème est dans NP, nous avons alors de bonnes raisons de nous opposer à la recherche d'une solution, car l'algorithme, en général, prendrait tout simplement trop de temps pour résoudre le problème.

Sommaire

Dans cet examen de complexité, nous avons défini les classes de problèmes P et NP. P représente de manière informelle les problèmes qui peuvent être efficacement résolus par un ordinateur tandis que NP représente ceux qui sont efficacement vérifiables.

Personne n'a pu prouver que P n'est pas égal à NP. La question de savoir si ces deux classes de problèmes sont équivalentes est connue sous le nom de problème P vs NP , et c'est le problème ouvert le plus important en informatique théorique aujourd'hui, sinon dans toutes les mathématiques. En fait, en 2000, le Clay Math Institute a désigné le problème P contre NP comme l'une des sept questions ouvertes les plus importantes en mathématiques et a offert une prime d'un million de dollars pour une preuve qui détermine la solution à ce problème.

Conclusion

Dans cet article, nous avons plongé dans les domaines de la calculabilité et de la complexité, en répondant à de grandes questions telles que "Qu'est-ce qu'un ordinateur?" Bien que les détails puissent être accablants, il y a un certain nombre de points importants à retenir :

• Il y a certaines choses qui ne peuvent tout simplement pas être calculées, comme le problème de l'arrêt.

• Il y a certaines choses qui ne peuvent pas être calculées efficacement, comme les problèmes dans NPC.

Plus importantes que les détails sont les façons de penser au calcul et aux problèmes de calcul. Dans nos vies professionnelles et même dans notre quotidien, nous pouvons rencontrer des problèmes jamais vus auparavant, et nous pouvons utiliser des outils et des techniques éprouvés pour déterminer le meilleur plan d'action.

Lectures complémentaires sur le blog Toptal Engineering :

• Comment aborder la rédaction d'un interprète à partir de zéro