Dans la vie j'aime écrire. Et j'aime les maths. Bon, ça dépend quels domaines en particuliers (détails à venir).
Les maths sont pleines de choses bizarres. Vraiment bizarres. Donc marrantes. Intrigantes. Stupéfiantes. Renversantes. Bouleversifiant...
On a déjà parlé de problèmes "indécidables". Vous cherchez un algorithme qui, sur une entrée d'une certaine forme, répond à une certaine question. Parfois un tel algorithme n'existe pas.
Nous avons vu que la source fondamentale du problème était un paradoxe similaire à celui de Jean-Neige (ou Russell), concernant les machines de Turing.
Parce qu'une machine de Turing, aussi puissante soit-elle, ne peut pas résoudre tous les problèmes. En particulier le problème de l'arrêt des machines de Turing.
Vous avez envie de croire, comme pour les énoncés indémontrables de Gödel, que les problèmes indécidables ne sont pas ni nombreux que ça. Détrompez-vous. Ça fait trois mois que je cherche des résultats d'indécidabilité. J'ai appris à les sentir. À repérer leur odeur.
Gudule : on avait dit de ne pas s'étendre sur votre trépidante vie scientifique, maître.
Je m'en fiche que tu t'en fiches, Gudule, c'est la vérité : l'indécidabilité est partout. Vérifiez sous votre lit avant d'aller dormir ce soir. Pour l'heure, voici quelques exemples pas piqués des hannetons.
Le dixième problème de Hilbert
Étant donné une équation polynomiale à plusieurs variables (mais coefficients entiers), existe-t-il une solution entière ?
Prouvé indécidable par Matiyasevich en 1970. Vous n'avez donc pas d'algorithme pour répondre en général à cette question.
Si vous suivez toujours, la « raison » fondamentale de l'indécidabilité (du moins de tous les problèmes indécidables que je connais) c'est d'être plus général que le problème de l'arrêt. D'une certaine manière, vous pouvez cacher des machines de Turing dans des équations polynomiales de façon à avoir :
"si j'ai un algorithme pour le 10e problème de Hilbert, alors je peux résoudre le problème de l'arrêt."
Oui. Des machines de Turing. On peut cacher des machines de Turing plus souvent que vous ne l'imaginez.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
La correspondance de Post.
Ce problème est le suivant : vous vous donnez des chaînes de caractères qui vont par paires de 2 (nombre et taille quelconques).
a1, a2, ... an
b1, b2, ... bn
(Imaginez des pièces avec en haut a, en bas b)
Et vous voulez savoir s'il est possible, avec ces pièces (que vous avez chacune en quantité infinie), de les mettre bout à bout de façon à avoir la même chaîne « a » et la même chaîne « b ».
Par exemple :
lalarbin, le, gudu
rbin , la, gudulele
Ça donne :
gudu le le lalarbin
gudulele la la rbin
Gudule :perfect match ! mais j'ai peur de comprendre.
Voilà, si vous cherchiez une idée de jeu amusant pour occuper vos futurs enfants pendant que vous installez Debian sur votre PC, pensez à la correspondance de Post.
Donc, ça a l'air facile comme ça, mais c'est indécidable. Il n'y a pas d'algorithme (même si vous n'avez que deux caractères 0 et 1). Pour vous en convaincre, songez que vous ne savez pas vraiment combien de fois les différentes chaînes de caractères vont être répétées...
La multiplication des matrices.
Les matrices (en anglais, matrix) sont des objets très naturels en algèbre. Ce sont des tableaux de nombres, que l'on a tendance à voir comme décrivant certaines transformations (symétries, rotations dans l'espace par exemple), ce qui rend naturelle leur opération de multiplication : multiplier deux matrices, c'est composer les deux transformations qu'elles représentent. Les connaisseurs savent que les matrices sont des représentations parfaites pour les applications linéaires d'espaces vectoriels de dimension finie.
Oups ! Cette image n'est pas conforme à nos directives de contenu. Afin de continuer la publication, veuillez la retirer ou mettre en ligne une autre image.
Mais nous, ça ne nous intéresse pas vraiment ici.
La multiplication des matrices est associative (vous pouvez oublier les parenthèses), mais non commutative (vous ne pouvez pas permuter les facteurs à volonté), et vous pouvez avoir un produit nul alors que les deux matrices ne le sont pas.
Le problème que nous posons maintenant est le suivant : étant donné un entier n, et un ensemble de matrices à n lignes et n colonnes à coefficients entiers, pouvez-vous par multiplication de ces matrices entre elles, obtenir une matrice nulle ?
Cette question est indécidable.
C'est aussi indécidable si vous avez un ensemble de 7 matrices 3 fois 3 à coefficients entiers.
(J'ai même une référence pour ça : http://www-math.mit.edu/~poonen/papers/sampler.pdf)
Gudule : c'est du sérieux.
Du coup, pour des matrices 2 fois 2, on ne sait pas. Il y a plein de choses qu'on ne sait pas.
Voilà pourquoi j'adore les questions de décidabilité.
