Est-ce que mon chat est Turing-complet ?

Article original : 
Traductrice : Chloé Lourseyre

Cet article est une retranscription d’un Lightning Talk que j’ai donné à l’occasion de la CppCon2021

On va parler d’un sujet plus léger cette semaine, mais malgré tout important : est-ce que mon chat est Turing-complet ?

Peluche, enchantée

Peluche est un chat tout doux qui, suite à un concours de circonstances, habite dans ma maison.

Elle sera notre sujet de test aujourd’hui

Est-ce que Peluche est Turing-complète?

C’est quoi, « Turing-complet » ?

On dit qu’une machine est Turing-complète si elle peut émuler une machine de Turing. Toute machine qui est Turing-complète peut exécuter n’importe quel programme informatique¹.

Cela signifie que toute machine qui implémente les huit instructions ci-après est équivalente à n’importe quel ordinateur.

• . et , : Gestion des entrées et des sorties.
• + et - : Augmentation et diminution de la valeur contenue dans la cellule mémoire pointée².
• > et < : Déplacement vers la gauche ou vers la droite la cellule pointée sur le ruban de mémoire.
• [ et ] : Faire des boucles.

Si on arrive à prouver que Peluche peut exécuter ces huit instructions, on prouvera qu’elle est Turing-complète.

Preuve de la Turing-complétude

Entrées et sorties

D’abord, j’ai essayé d’obtenir une réaction en utilisant mon doigt :

Suite à cela, elle s’est tournée vers moi, m’a fixée quelques secondes, puis s’est détournée de moi.

Donc voilà : je l’ai pokée et j’ai obtenu une réaction. Elle peut donc computer des entrées et renvoyer une sortie.

Entrée/sortie : check !

Augmentation et diminution d’une valeur en mémoire

L’autre jour, en rentrant du travail, j’ai découvert ceci :

Des croquettes partout…

Mais en y regardant de plus près, j’ai remarqué quelque chose d’intéressant. Si on numérote les dalles de carrelage comme suit :

Cela ressemble fortement à un ruban de mémoire, si le nombre de croquettes contenu correspond à la valeur mémorisée ! Et comme elle n’hésite pas à les manger à même le sol, elle peut tout aussi bien faire diminuer cette valeur.

Augmentation/diminution de mémoire : check !

Déplacement vers la gauche ou la droite du ruban de mémoire

Un jour lointain, je faisais la vaisselle lorsque j’ai accidentellement renversé de l’eau sur Peluche. Elle s’est mise à courir partout et a mis le bazar dans la cuisine.

Si vous regardez bien (en suivant la flèche rouge), vous remarquerez qu’elle a déplacé son bol à croquette.

De fait, cela signifie que lorsqu’elle renversera ses croquettes sur une autre dalle de carrelage que la première, c’est-à-dire ailleurs sur la bande mémoire.

Déplacement de la bande mémoire : check !

Les boucles

Bon, après ce bazar j’ai (évidemment) dû tout nettoyer.

Mais pas plus de cinq minutes après avoir fini de nettoyer, je me suis retrouvée devant ça :

Okay… Elle peut SANS AUCUN DOUTE faire des boucles.

Boucles : check !

Nous venons de prouver que Peluche est Turing-complète. Du coup, la question qui se pose est : comment l’exploiter pour effectuer des calculs de haute performance ?

Que faire avec elle ?

Peluche est Turing-complète : ça veut dire qu’on peut faire ce qu’on veut avec !

J’ai alors essayé de lui donner un morceau de code simple à exécuter, pour tester³:

😾😾😾😾😾😾😾😾
😿
🐈😾
🐈😾😾
🐈😾😾😾
🐈😾😾😾😾
🐈😾😾😾😾😾
🐈😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾😾😾😾😾😾
🐈😾😾😾😾😾😾😾😾😾😾😾😾😾😾😾😾
😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻🐾
😸
🐈🐈🐈🐈🐈🐈🐈🐈🐈🙀😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🐾🐾🙀😾😾😾😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🐾🐾🐾🙀😾😾😾😾😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🐾🐾🐾🙀😾😾😾😾😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🙀😾😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🙀😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🙀😾😻😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🙀😾😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈😾😾🙀🐾🐾😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🐾🐾🐾🙀😾😾😾😾😻😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐈🐾🐾🐾🐾🙀😾😾😾😾😻😻😻😻😻😻😻😻😻😻😻😻😻
🐈🐈🐈🐈🐈🐈🐾🐾🙀😾😾
😻😻😻😻😻😻🙀

Le résultat était sans appel : elle n’a pas voulu bouger.

Au final, peut-être que les chats ne sont pas conçus pour exécuter du code ? Et ce, même s’ils sont Turing-complets ?

À propos de la « chat-formatique »

Blague à part, la chat-formatique (ou cat-computing) est le nom que je donne à cette pratique généralisée. D’expérience, il arrive assez souvent que quand quelqu’un découvre une nouvelle fonctionnalité du langage, iel commence à l’utiliser à tors et à travers. Juste parce qu’iel le peut.

Cependant, tout comme vous pouvez exécuter du code avec un chat⁴ mais ne devriez pas, ce n’est pas parce que vous pouvez utiliser une fonctionnalité que vous devriez.

En conclusion

La chat-formatique peut sembler être une erreur de débutant (et ça l’est), mais même le plus grand·e·s expert·e·s commettent des erreurs de débutant de temps à autre (et il n’y a pas de honte à cela).

Tous les trois ans, une nouvelle version du C++ est publiée. À chaque fois, ça me donne envie d’utiliser les nouvelles fonctionnalités partout, dans tous mes programmes. Bien que ce soit une opportunité pour gagner de l’expérience sur ces fonctionnalités, c’est aussi un terrain favorable à l’acquisition de mauvaises pratiques.

Demandez-vous toujours si une fonctionnalité est nécessaire⁵ avant de l’utiliser, sinon vous pourriez être en train de faire de la chat-formatique.

Vos savants étaient si préoccupés par ce qu’ils pourraient faire ou non qu’ils ne se sont pas demandé s’ils devraient le faire⁶.

Docteur Ian Malcolm, Jurassic Park

Aussi, la chat-formatique c’est de la maltraitance animale, ne le faites pas 😠 !

Merci de votre attention et à la semaine prochaine !

Article original : 
Traductrice : Chloé Lourseyre

Addendum

Notes

1. Ceci est une définition simplifiée et vulgarisée, mais suffisante pour le bien cet article. Si vous voulez la vraie définition, suivez le lien suivant : Turing completeness – Wikipedia
2. Je ne l’ai pas mentionné explicitement, mais une machine Turing a un « ruban de mémoire », contenant des « cellules de mémoire ». La machine pointe toujours vers une cellule, qui est désignée comme la cellule « pointée ».
3. Vous n’arrivez peut-être pas à lire ce morceau de code — il s’agit d’un joli nouveau langage que j’ai baptisé « braincat ».
4. Oui, je sais, dans la vraie vie, vous ne pouvez pas exécuter du code avec un chat. Mais pour le bien de la métaphore, essayez d’imaginer que vous pouvez.
5. Bien, la « nécessité » survient quand il y a un bénéfice net à l’emploi d’une fonctionnalité. On ne parle pas ici de nécessité absolue mais de nécessité pratique.
6. Ce n’est pas exactement phrase que prononce docteur Malcolm dans le film. En français, la phrase complète est : « Vos savants étaient si préoccupés par ce qu’ils pourraient faire ou non qu’ils ne se sont pas demandé s’ils en avaient le droit. ». Afin de mieux adhérer au contexte, j’ai pris la liberté de la retraduire depuis la version originale, qui est : « They were too busy wondering if they could to think about whether they should. »