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...
Pour commencer, Gudule va vous spoiler leur contenu. Vas-y, Gudule.
Gudule : c'est trop bien.
Merci Gudule.
1. Charlot 2
Depuis les années 30 et l'invention du lambda-calcul, ainsi que des machines de Turing (merci qui ?), nous avons une notion assez bien arrêtée de ce qu'est un calcul, formalisée en la personne de Charlot le petit robot.
Charlot lit et écrit des trucs sur un ruban infini en fonction de ce qu'on lui a demandé de faire. Il calcule.
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.
Vous pouvez aussi imaginer, pour faire encore plus simple, Charlot 2. Il dispose d'une entrée qui contient des 0 ou des 1 (je dirai un « mot », parce qu'une chaîne de caractères, c'est un mot), et il effectue certaines opérations en fonction de ses instructions. Dans le monde booléen, 0 est « faux », 1 est « vrai ».
Les opérations OU, ET, NON sont alors formalisées par des « portes logiques », et on peut faire de superbes petits diagrammes avec des petits fils joignant les portes et aboutissant au résultat. D'ailleurs, on apprend même au passage que toutes les opérations peuvent être simulées à l'aide de portes NAND (AND puis NON sur le résultat). C'est amusant, mais c'est assez facile à démontrer.
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.
Imaginons que nous ayons une fonction f, par exemple une fonction qui dit « oui » si le mot en entrée ne contient que des 1 et « non » sinon. Dire que nous pouvons calculer f, c'est dire que sur n'importe quelle taille de mot en entrée, il nous est possible de construire un circuit pour Charlot 2 qui effectue ce calcul, donc qui finisse par une sortie sur laquelle on peut lire le résultat : 0 ou 1.
Quant à savoir si on fait ce calcul rapidement... on va s'astreindre à construire un tel circuit sans prendre trop de temps, ou construire un circuit pas trop gros. (Parce que sinon, ce serait stupide, on encoderait directement le résultat : "si l'entrée est xxx renvoyer yyy", et on ferait ça pour toutes les entres possibles. Gros, gros circuit !).
