Les machines de Turing

GNU/Linux Magazine n° 174 | août 2014 | Nicolas Prcovic
Creative Commons
  • Actuellement 0 sur 5 étoiles
0
Merci d'avoir participé !
Vous avez déjà noté cette page, vous ne pouvez la noter qu'une fois !
Votre note a été changée, merci de votre participation !
Y a-t-il des problèmes qu'aucun ordinateur ne pourra jamais résoudre et quels sont-ils ? Pour que les théoriciens puissent répondre à ce type de questions fondamentales, ils bénéficient d'un modèle de calcul à la fois suffisamment puissant pour représenter n'importe quel programme, mais aussi extrêmement simple, ce qui permet de raisonner plus facilement sur les propriétés générales des programmes : la machine de Turing. À travers de nombreux exemples, cet article vous familiarisera avec les machines de Turing et vous donnera quelques-unes de leurs propriétés fondamentales.

Si son papy demande à Kevin (votre petit voisin geek qui passe ses journées à découvrir de nouvelles choses à programmer) ce qu'on peut faire avec un ordinateur, il y a toutes les chances qu'il réponde « tout ». Kevin, qui n'a pas encore eu l'occasion de s'intéresser à l'informatique théorique, à tort : il existe des problèmes qu'aucun ordinateur ne saurait résoudre (même avec un processeur plus rapide, même avec plus de mémoire, même sous Linux, même si Kevin est un génie).

Avant que l'informatique n'existe, la question de ses limites était posée dans l'autre sens : comment définir une machine capable de résoudre automatiquement le maximum de problèmes possibles ? C'est ainsi qu'un certain nombre de mathématiciens se sont mis à chercher les modèles de calcul les plus puissants possibles. En 1936, Alan Turing définit une machine abstraite qui portera son nom et qui sert de modèle à tous les ordinateurs depuis leur création et encore de nos jours.

Mais tout d'abord, expliquons ce qu'on appelle puissance dans le contexte de la calculabilité. Si on considère deux modèles de calcul A et B, on dit que A est plus puissant que B si l'ensemble des problèmes que B peut résoudre est inclus dans celui de A. Un modèle de calcul sait résoudre un problème s'il peut coder un algorithme qui donnera la solution du problème en un temps fini (mais éventuellement très long). Nous verrons par exemple que la machine de Turing est plus puissante que la machine de Mealy.

Note

Ici, puissance n'est pas vitesse !

Il ne faut pas confondre cette notion de puissance avec celle qu'on utilise habituellement à propos d'un ordinateur, qu'on dit puissant parce qu'il est rapide ou parce qu'il a beaucoup de mémoire. En pratique, il est vrai qu'il ne suffit pas qu'on sache résoudre un problème en temps fini. Il faut pouvoir le résoudre en un temps acceptable (disons moins de 10 milliards d'années, si possible). Plus un ordinateur est rapide, plus il peut résoudre de problèmes en un temps acceptable. Mais si on ne tient pas compte du temps, ce n'est pas en le rendant plus rapide qu'un ordinateur résoudra plus de problèmes.

Un bon modèle de calcul n'est pas celui qui permet d'écrire des programmes courts et efficaces, mais qui permet de décrire n'importe quel programme à l'aide de quelques notions très élémentaires. Grâce à cette simplicité, il est plus facile d'étudier les propriétés des ordinateurs et de répondre à des questions fondamentales sur ce qu'ils sont capables de faire.

1. Les machines de Turing

Une machine de Turing (MdT) est une machine composée d'un système de contrôle, d'une tête de lecture/écriture et d'un ruban de longueur infinie (Fig. 1). Le ruban fait office de mémoire : c'est une suite de cases, chacune pouvant contenir un symbole. Chaque machine de Turing est définie par un ensemble Q d'états, par les symboles qu'elle peut lire et écrire sur le ruban et par une fonction de transitions. La fonction de transitions fait office de programme (mais c'est un programme figé, comme s'il était en ROM). Elle est définie par un ensemble d'informations de la forme (q, s) => (q', s', d). En fonction de l'état q où la machine se trouve actuellement et du symbole s pointé par la tête de lecture, le système de contrôle détermine le nouvel état q' dans lequel va passer la machine, le symbole s' qui va remplacer celui actuellement pointé et le déplacement d de la tête de lecture (une case vers la droite ou vers la gauche).

Fig 1 : Représentation d'une machine de Turing

Initialement, la tête de lecture pointe sur le premier symbole d'une suite finie de symboles encadrée à gauche et à droite par deux suites infinies de cases vides. Cette suite de symboles constitue la donnée d'entrée de la machine de Turing. Au départ, la machine se trouve toujours dans le même état initial q0. Elle s'arrêtera si elle atteint un état final qf. À ce moment-là, ce qui se trouve sur le ruban constituera le résultat de la machine.

Pour représenter une machine de Turing particulière, on peut utiliser un diagramme de transitions (Fig. 2 et suivantes). Son dessin contient tous les états (leurs noms dans des cercles) reliés entre eux par des flèches. Une flèche étiquetée s ;s',d reliant l'état q à l'état q' indique la transition (q, s) => (q', s', d). L'état pointé par un triangle est l'état initial. Un état doublement cerclé est final.

Vous conviendrez que décrire une procédure de calcul uniquement à l'aide de transitions de la forme (q, s) => (q', s', d) est très rudimentaire (en tout cas beaucoup plus rudimentaire qu'à l'aide d'un programme écrit dans n'importe quel langage de programmation). Et pourtant, la machine de Turing étant le modèle de calcul qui sert de base à tous les ordinateurs depuis les débuts de l'informatique, vous pouvez réécrire n'importe lequel de vos programmes sous la forme d'un diagramme de machine de Turing. Néanmoins, je ne vous le conseille pas, car même des calculs pas trop compliqués peuvent nécessiter plus d'efforts que de faire une Tour Eiffel avec des allumettes ! Par contre, ceux qui aiment apprendre de nouveaux langages de programmation trouveront peut-être amusant de trouver comment « programmer » quelques petits algorithmes sous la forme de machines de Turing.

Voyons maintenant quelques exemples. Dans ceux-ci, afin de réduire la taille de nos machines, nous représenterons tous les nombres en binaire (base 2).

Note

Rappel sur la représentation binaire

La représentation binaire consiste à n'utiliser que deux chiffres (0 et 1), appelés bits, pour représenter les valeurs. Les premiers entiers « binaires » sont donc : 0 (=0), 1 (=1), 10 (=2), 11 (=3), 100 (=4), 101 (=5), etc.

Toutes les machines de Turing (et de Mealy, cf. plus bas) dont nous donnons les diagrammes ont été créées et testées avec le logiciel JFLAP sous licence Creative Commons (l'exécutable Java est téléchargeable à l'adresse http://www.jflap.org).

Notre premier exemple effectue l'incrémentation (addition de la valeur 1) d'un nombre fourni en entrée. Incrémenter un nombre binaire, c'est remplacer le bit le plus à droite par 1 si c'était un 0. Mais si c'était un 1, ce bit passe à 0 et l'incrémentation doit se poursuivre à partir du bit précédent (à gauche).

Fig. 2 : MdT réalisant une incrémentation (les petits carrés représentent les cases vides du ruban, celles qui ne contiennent aucun symbole d'entrée au départ).

Notre deuxième exemple calcule la somme de deux entiers (toujours en représentation binaire). En entrée, on fournit les bits du premier entier, suivi du symbole +, suivi des bits du deuxième entier. Le principe du calcul est de décrémenter le deuxième entier, puis d'incrémenter le premier entier et on recommence, jusqu'à ce qu'on se rende compte qu'à un moment le deuxième entier qu'on est en train de décrémenter était nul (une suite de zéros). Alors on s'arrête, car le premier entier est égal à la somme des deux entiers du début.

Fig. 3 : MdT réalisant une addition

Je vous laisse en exercice (plus difficile) les machines de Turing qui font la multiplication, effectuent des logarithmes, vous apportent le café. Il est évident que des exemples seuls ne permettent pas d'indiquer clairement tout ce qu'on peut faire avec une machine de Turing. Mais avant d'étudier ce que peut et ne peut pas calculer une machine de Turing, je vais présenter la machine de Mealy, un modèle de calcul moins puissant. Nous verrons ce que peuvent déjà faire les machines de Mealy et ce qui caractérise les problèmes qu'elles peuvent résoudre. Cela nous permettra de bien saisir ce que les machines de Turing peuvent faire de plus, et à quel prix.

2. Les machines de Mealy

Bien qu'historiquement la machine de Mealy ait été définie indépendamment de la machine de Turing, on peut la voir comme une simplification de cette dernière. La différence fondamentale est que la tête de lecture va toujours vers la droite : les symboles ne sont lus qu'une fois chacun, du premier au dernier, de la gauche vers la droite. En conséquence, il n'est plus nécessaire de remplacer chaque symbole lu par un nouveau symbole, puisque ce dernier ne sera jamais relu. Si on veut conserver les données d'entrée, on peut définir deux rubans : un ruban de lecture et un ruban d'écriture. Nous avons donc une suite de symboles qui servent de données d'entrée et une suite de symboles écrits qui représentent le résultat du calcul. Enfin, il n'y a pas besoin de définir d'état final puisque la machine s'arrête automatiquement dès qu'elle a lu le dernier symbole d'entrée.

Comme premier exemple, voici une machine de Mealy qui indique la suite de mouvements à effectuer pour sortir d'un labyrinthe. La méthode consiste à avancer en longeant constamment le mur situé à sa gauche (Fig. 4). Un mouvement est soit une avancée d'une case (symbole a), soit un quart de tour à gauche (symbole g) ou à droite (symbole d). Avant chaque mouvement, on n'a besoin que de savoir si actuellement il y a un mur à sa gauche et/ou devant soi. On a donc 4 informations possibles : un mur à gauche et devant (T), seulement un mur à gauche (I), seulement un mur devant (symbole -), aucun mur (symbole  ).

Fig. 4 : Cheminement dans un labyrinthe en longeant les murs situés à gauche. Le dessin ci-dessus donne les déplacements à effectuer. Chaque flèche correspond à une avancée d'une case. On n'a pas indiqué les quarts de tour. Au départ, on se trouve dans la case du bas dans le labyrinthe et on est orienté vers le haut. Voici la séquence des entrées et des sorties correspondant à la solution donnée sur le dessin : T:d, I:a, 0:g, 0:a, -:g, 0:a, I:a, -:g, 0:a, T:d, T:d, I:a, I:a, T:d, I:a, 0:g, 0:a

Voici la méthode utilisée pour trouver un chemin. Pour déterminer quel mouvement effectuer, il faut d'abord savoir si on vient d'avancer ou si on vient de tourner.

Si on vient d'avancer :

- S'il n'y a pas de mur à gauche, on tourne à gauche.

- S'il y a un mur à gauche mais pas devant, on avance.

- S'il y a un mur à gauche et un mur devant, on tourne à droite.

Si on vient de tourner (à gauche ou à droite) :

- S'il n'y a pas de mur devant, on avance.

- S'il y a un mur devant et à gauche, on tourne à droite.

- (Le cas où il n'y aurait aucun mur ne peut pas arriver. Je vous laisse vérifier pourquoi.)

La figure 5 présente une machine de Mealy qui met en œuvre cette méthode.

Fig. 5 : Cheminement dans un labyrinthe avec une machine de Mealy en longeant les murs situés à gauche

Maintenant, nous allons définir à nouveau un incrémenteur. Nous ne pouvons pas reprendre tel quel celui que nous avons défini avec une machine de Turing. En effet, cette machine faisait se déplacer la tête de lecture de gauche à droite jusqu'au dernier chiffre, puis modifiait les chiffres un par un en se déplaçant toujours vers la gauche. Comme une machine de Mealy ne peut se déplacer que de la gauche vers la droite et jamais revenir en arrière, ne sommes-nous pas coincés ? Une simple astuce résout le problème : il suffit de coder l'entrée en présentant les chiffres dans l'ordre inverse. Ainsi, au départ, la machine de Mealy se trouve déjà positionnée sur le chiffre des unités et elle effectue les mêmes transitions en se déplaçant de gauche à droite que lorsque la machine de Turing se déplaçait de droite à gauche. Évidemment, le résultat en sortie doit être décodé en lisant le résultat de droite à gauche. Par exemple, si on veut obtenir le successeur de 100111, on présente la séquence inversée 111001, la machine produit 000101, qu'il faut décoder en ré-inversant comme étant 101000. La machine de Mealy est en figure 6.

Fig. 6 : Incrémentation avec une machine de Mealy

Peut-on effectuer une addition ? Oui, mais il faut effectuer le calcul d'une autre manière que celui que nous avons vu pour la machine de Turing. En effet, celle-ci effectuait des allers-retours et l'astuce simple qui fonctionnait pour l'incrémentation ne marche plus. Cependant, une fois encore, en changeant l'ordre des données fournies en entrée, on va pouvoir faire un calcul qui ne nécessite pas de faire des allers-retours sur un ruban. L'algorithme est celui qu'on utilise lorsqu'on fait une addition à la main : on additionne les unités, puis on additionne les dizaines en prenant en compte la retenue, etc. Pour qu'une machine puisse faire cette addition en une seule passe de gauche à droite, il faut ordonner en entrée les chiffres des deux entiers A et B à additionner dans l'ordre dont on a besoin de les lire : unité de A, unité de B, dizaine de A, dizaine de B, etc. La machine de Mealy est en figure 7.

Fig. 7 : Addition avec une machine de Mealy

Peut-on effectuer des multiplications ? Oui, sous la condition qu'un des deux entiers soit une constante et que seul le deuxième entier soit la donnée d'entrée. Mais plutôt que de vous donner tout de suite un exemple de multiplicateur, je vais vous expliquer comment en définir un quelle que soit la constante à multiplier et, de façon plus générale, comment définir des machines de Mealy plus complexes à partir de machines de Mealy plus simples.

Considérons deux machines de Mealy M1 et M2, qui calculent respectivement les fonctions f1 et f2. On peut définir la machine de Mealy M3 permettant de calculer f3, la composée de f1 et f2 : si x est donnée en entrée de M2, on a y = f2(x) en sortie, et si y est donnée en entrée de M1, on a z=f1(y)=f1(f2(x)) en sortie. Voici comment définir M3 à partir de M1 et M2. L'idée est qu'on pourrait très bien construire M3 en « branchant » la sortie de M2 sur l'entrée de M1. Lorsque M2 lit un symbole, elle en écrit un en sortie, lequel est immédiatement lu par M1, qui écrira à son tour un symbole en sortie. Donc, quels que soient les états A, B, C et D, et les symboles s, t et u, si dans M2, il y a une transition entre les états A et B en lisant s et en écrivant t, et si dans M1, il y a une transition entre les états C et D en lisant t et en écrivant u, alors dans M3, il y a une transition entre les états (A,C) et (B,D) en lisant s et en écrivant u. Un exemple (très artificiel, mais facile à comprendre) de composition de machines de Mealy se trouve en figure 8.

Fig. 8a : Machine de Mealy F1

Fig. 8b : Machine de Mealy F2

Fig. 8c : Composition des machines de Mealy F1 et F2

Quels types de calculs peut-on effectuer grâce à une machine de Mealy ? Pour commencer à répondre à cette question, il faut d'abord constater que la taille de la donnée de sortie est égale à celle de la donnée d'entrée. Avec un peu d'astuce (que nous verrons plus loin), on peut réduire cette contrainte d'égalité des tailles : la taille de la sortie n'a besoin que d'être proportionnelle à la taille de l'entrée. Ainsi, a priori, on peut envisager faire une addition de deux entiers sur n et m bits (résultat sur max(n,m)+1 bits), voire une multiplication (n+m bits), mais pas le calcul de nm (résultat sur n X m bits).

Ces considérations sur le rapport entre la taille de la donnée d'entrée et la taille de la donnée de sortie nous amènent déjà à pouvoir affirmer que toute fonction dont la taille des données d'entrée et de sortie est bornée par une constante est calculable par une machine de Mealy. Voici pourquoi. Si les tailles des entrées et sorties sont bornées, rien ne nous empêche d'expliciter la liste des couples (x, f(x)). Imaginons par exemple que l'on veuille définir une machine qui calcule le carré d'un entier E compris entre 0 et 3. Voici la table explicitant cette fonction (on continue à représenter les entiers en base 2) :

E e1 e0 s3 s2 s1 s0 S = E2
0 0 0 0 0 0 0 0
1 0 1 0 0 0 1 1
2 1 0 0 1 0 0 4
3 1 1 1 0 0 1 9

La machine qui modélise la fonction carré lit une entrée codée sur 6 symboles : les deux premiers sont les bits du nombre à mettre au carré et les quatre suivants sont (arbitrairement) des x servant à faire avancer la machine le temps qu'elle écrive le résultat. Le résultat est codé sur 6 symboles : les deux premiers sont des x qui sont écrits le temps que l'entier donné en entrée soit entièrement lu et les quatre derniers sont les bits du résultat de la fonction. Par exemple, si on veut calculer le carré de 3, on fournit 11xxxx en entrée et on obtient xx1001 en sortie. On aurait pu définir une machine bien plus optimisée (avec moins d'états), mais j'ai préféré utiliser la méthode la plus générale qui fonctionne quel que soit le calcul à effectuer. Pour définir une machine, on crée d'abord tous les états et suites de transitions correspondant à toutes les données d'entrée. À chaque transition, un symbole d'entrée est lu et un caractère quelconque (x) sans signification est écrit. À chaque suite de symboles d'entrée va donc correspondre un état unique depuis lequel on va créer une suite d'états et de transitions destinés à écrire la sortie (le résultat du calcul correspondant à la donnée d'entrée précédemment lue).

Fig. 9 : Machine de Mealy calculant un carré

Note

Cette façon de créer une machine peut sembler décevante : on n'effectue pas un calcul dans un sens traditionnel (description d'une suite d'opérations), mais à partir d'une table où sont « pré-calculés » les résultats. Ce n'est pas la machine qui calcule, c'est l'humain qui a déjà tout calculé et la machine qui a mémorisé les résultats et se contente de les écrire. Il ne faut pas considérer l'intérêt pratique de cette façon de définir les machines, mais le fait qu'au pire c'est toujours possible de pouvoir faire comme ça.

Qu'en est-il des calculs qui ne présupposent pas que la taille de l'entrée soit bornée ? Par exemple, les fonctions définies sur tous les entiers, ou les programmes effectuant des opérations sur n'importe quel texte, image ou son ? Il s'avère que l'ensemble des problèmes calculables par une machine de Mealy est caractérisable par ce qu'on appelle une expression régulière (ou rationnelle), mais nous n'entrerons pas dans ces détails inutilement complexes dans le cadre de cet article. Nous nous contenterons de faire la remarque suivante : à partir du moment où on est capable de trouver des machines de Mealy sachant résoudre un certain nombre de problèmes élémentaires, il est possible de les composer pour qu'elles résolvent des problèmes plus complexes.

Par exemple, si on sait faire la machine de Mealy qui multiplie un entier binaire par 2 (il suffit d'ajouter un 0 à droite du nombre) et une machine effectuant la somme de deux entiers (nous l'avons vue précédemment), on peut définir par composition une machine qui multiplie tout entier x par 2, puis faire la somme entre 2x et x pour obtenir 3x. On peut de même faire une machine de Mealy pour obtenir 4x, une autre machine pour obtenir 5x, etc. Mais si nous voulons définir une machine de Mealy qui effectue le produit xyx et y sont deux entiers de longueur quelconque fournis en entrée ? C'est impossible, car la façon d'exprimer ce calcul implique une définition récursive, précisément l'exécution d'une boucle dont le nombre d'itérations dépend d'une des données d'entrée. Il nous faut une machine de Turing pour cela.

3. Puissance vs temps de calcul

Quel masochisme peut inciter quiconque à chercher à résoudre un problème en utilisant une machine de Mealy plutôt qu'une machine de Turing, qui donne plus de facilité et de possibilités de le modéliser ? En effet, si on compare nos exemples de machines de Turing et de Mealy qui réalisent l'addition, on peut constater que la machine de Turing a été plus simple à concevoir que celle de Mealy. Mais les machines de Mealy ont l'avantage de garantir un temps de calcul proportionnel à la taille de la donnée d'entrée, ce qui n'est pas du tout le cas des machines de Turing. Cette caractéristique fait que tout problème résolvable par une machine de Mealy est donc rapide à résoudre. En effet, en exagérant à peine, dès qu'on a terminé de lire la donnée d'entrée, on obtient le résultat. L'intérêt d'essayer d'utiliser le modèle de la machine de Mealy est de se permettre de trouver le calcul le plus rapide pour traiter un problème. Lorsque j'ai défini une machine de Turing pour effectuer une addition grâce à une succession d'incrémentations et de décrémentations, je ne me suis pas fatigué le cerveau, mais j'ai obtenu une machine qui fait une addition en un temps exagérément long : si le deuxième nombre à additionner possède n chiffres, il faut environ n2 étapes de calcul au lieu de n avec la méthode utilisée pour la machine de Mealy.

Ainsi, plus un modèle de calcul est puissant, plus les méthodes de calcul qu'il autorise sont susceptibles d'être longues à exécuter. Dans le cas des machines de Turing, ce temps peut même être infini ! Il existe bien d'autres modèles de calcul intermédiaires en termes de puissance entre les machines de Mealy et de Turing (par exemple, les automates à pile, les machines de Turing dont la taille du ruban est une fonction polynomiale de la taille d'entrée, …) et d'autres modèles de calcul qui sont très différents, mais s'avèrent équivalents aux machines de Turing (ex : automates cellulaires, grammaires formelles, lambda-calcul, etc.). Mais les étudier ici dépasserait le cadre d'une introduction aux machines abstraites. La machine de Mealy est le modèle le moins puissant qu'on puisse envisager. Il est en effet difficile d'imaginer une machine qui fasse moins que lire au moins une fois tous les symboles de la donnée d'entrée. Par contre, il peut sembler surprenant que le modèle de la machine de Turing n'ait jamais été dépassé depuis sa création en 1936 malgré plusieurs tentatives (dont il a été à chaque fois démontré qu'elles n'étaient qu'aussi puissantes que la machine de Turing, et pas plus). On pense d'ailleurs généralement qu'on ne peut pas trouver mieux. Voyons maintenant pourquoi les machines de Turing sont si puissantes et les inconvénients que cela implique.

4. Les programmes qui n'existent pas

Le simple fait qu'une machine de Turing puisse revenir en arrière lui permet de répéter des calculs un nombre de fois qui dépend d'une donnée d'entrée. Mais plus fondamentalement, elle peut réaliser n'importe quelle fonction récursive.

Note

Rappel sur les fonctions récursives

Est récursif ce qui se définit par rapport à lui-même. Par exemple, un nombre est constitué d'un chiffre accolé éventuellement à un nombre ; un homme est le fils d'un homme et d'une femme ; un entier est soit zéro, soit le successeur d'un entier. Définition récursive de mul(x,y) la multiplication de x par y :

- mul(x, 0) = 0

- pour tout y > 0, mul(x, y) = mul(x, y – 1) + x.

Or, cette possibilité de définir a priori n'importe quelle fonction récursive ne garantit pas qu'on obtienne toujours un résultat. Par exemple, il est très possible de définir une fonction qui va boucler indéfiniment. Ex : une fonction f telle que si x est pair alors f(x) = f(x+1) et si x est impair alors f(x) = f(x-1). On a f(2) = f(3) = f(2) = …

De façon générale, une fonction est dite calculable s'il existe une méthode mécanique qui permette de toujours obtenir un résultat en un temps fini. Autrement dit, une fonction f est calculable s'il existe une machine de Turing (ou de façon générale, un programme) qui donne la valeur de f(x) pour n'importe quel x, en un temps fini. Ce qui peut surprendre au premier abord est que certaines fonctions ne sont pas calculables. Dit autrement : certains programmes censés réaliser certaines fonctions ne peuvent pas exister.

Le problème de l'arrêt est l'exemple concret le plus connu. Imaginons que nous voulions réaliser la fonction halt(P,E) qui prend en argument n'importe quel programme P (un exécutable stocké sur votre disque dur, codé par une suite d'octets) et une donnée d'entrée E destinée à P. La fonction halt(P,E) retourne Vrai si le programme P s'arrête (il ne boucle pas infiniment) quand on lui fournit l'entrée E, et la fonction retourne Faux dans le cas contraire. Il a été démontré que cette fonction n'est pas calculable. Nous ne présenterons pas cette démonstration, mais nous signalons simplement que le point clé est que si halt(P,E) existait, alors il pourrait s'analyser lui-même, ce qui mènerait à un paradoxe dans certaines circonstances. Il est en théorie bien dommage que halt(P,E) ne puisse pas exister. Cela signifie que l'on ne peut pas informatiser complètement l'analyse sémantique de programmes (c'est-à-dire la capacité de comprendre ce qu'ils calculent) et la détection de bugs, vu qu'on ne saura même pas garantir que le programme ne reste pas coincé dans une boucle infinie ! Un compilateur peut vérifier que n'importe quel texte de programme respecte la syntaxe d'un langage, mais il n'existera jamais de programme qui saura toujours vérifier qu'il respecte bien des spécifications données. Attention : je n'ai pas écrit qu'il ne peut exister d'analyseurs sémantiques de programmes, mais qu'il existera toujours des programmes qui ne pourront pas être analysés par eux.

Conclusion

Non, un ordinateur ne peut pas tout faire, notamment pas quelques programmes qui pourraient être très utiles aux programmeurs. Ce résultat négatif fondamental en informatique, qui peut vous attrister si vous vouez un culte à votre ordinateur, a l'avantage de poser des limites à ce que votre chef de projet est en droit d'attendre de vous.