S.O.S (Sense-Of-Self)

Oulah, long time no see!

J'ai profité d'être cloué au lit avec angine et oreilles qui saignent pour réfléchir dans ma tête. Du coup lecteurs adorés, je vous écris ! L'arrêt maladie ça a du bon, tant que ça ne dure pas trop longtemps.

Pour une fois je ne me suis pas pris la tête avec des mots de passe, ou du vim ou du ROT13. Faut changer d'obsession de temps en temps. Du coup j'ai repris un vieux sujet datant de mes recherches fondamentales (genre). Il s’agit du sens du soi. Sense-Of-Self en anglais, ça fait tout de suite plus classe. D'autant que les initiales c'est "S.O.S" d'où le titre de ce billet. C'est bien ficelé hein ?

Version courte et compliquée

J'ai enfin trouvé un programme python dont l'uneek fonction est de se reconnaitre lui-même, et seulement lui-même. Pour la métaphore disons un "système immunitaire". Le voici en action :

$ cat sos.py
D='Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D])';Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D]) 
$ cat sos.py | python3 sos.py 
1 
$ echo "je suis un virus" | sos.py
0
À quoi ça sert ? Ben a rien comme d'hab. Sérieux, après toutes ces années à me lire vous posez encore la question ;)

Version longue et délicatement parsemée d'humour bien relou

Le Sense-Of-Self c'est la propriété qui permet à une entité de se distinguer elle-même de tout le reste. Le monde se divise alors en deux catégories : le soi et le non-soi.

Je suis reparti sur cette piste parce que je pensais notamment à toutes les conneries que fait mon organisme en ce moment : inflammation, système immunitaire survolté, allergies. Autant de réactions justement liées à ce fameux "sens-du-soi". Le stade ultime c'est les réactions auto-immunes où l'organisme s'attaque lui-même parce qu'il se prend pour du non-soi. Truc de ouf.

En terme informateek, le Sense-Of-Self prend une résonnance intéressante. De loin c'est peut-être lié à la question - autrement plus fumeuse - de la conscience des machines. Deux trois gugusses ont d'ailleurs vaguement réfléchi à ça : Alan Turing, John Von Neumann, Marvin Minsky, Andrei Kolmogorov... Plus récemment Raymond Smullyan, David Naccache(*), Adrian Perrig(*), etc. Du coup je me suis dit comme ça : euh, pourquoi pas moi ?

N'étant pas précisément équipé du même appareil cérébral que les personnes susnommées, je me suis contenté d'une version simplifiée du problème. Formalisons :

Existe-t-il un programme SOS qui affiche "1" lorsqu'il est appliqué à lui-même et qui affiche "0" lorsqu'il est appliqué à toute autre entrée ?

Autrement dit, le programme se reconnait lui-même (1) et fait la différence avec tout le reste (0). On aurait : SOS(SOS)=1 et SOS(other)=0.

De plus, je me suis demandé s'il existe un programme SOS qui ne fait QUE ça. Par exemple il n'en profite pas pour nous afficher en plus de la pub ou pour envoyer nos données personnelles sous forme de cookies à un serveur dans un autre pays. Je recherche un programme en quelque sorte minimal, qui se réduirait à la fonction Sense-Of-Self. Toujours dans l'esprit minimaliste, je voudrais que le programme soit court, voire même le plus court possible tant qu'on y est. Dans l'idée d'isoler l'essence même du sens-de-soi. "Isoler l'essence même du sens-de-soi" ça veut pas dire grand-chose mais j'adore écrire des phrases comme ça.

Les tas de lard

En bon geek, j'ai jeté un œil à l'état de l'art (voir illustration). Autant le reconnaitre, il existe déjà beaucoup de choses sur le sujet, notamment sous l'angle des "Quines". Un Quine (une Quine ?) c'est un programme autoreproducteur : il ne fait rien d'autre qu'afficher son propre code, sans aide extérieure. Comme une bestiole qui vomirait son ADN, et seulement son ADN. Pas comme moi au HellFest. On est déjà très proche de ce que je recherche. Moi je veux un programme qui reconnait son ADN au lieu de l'afficher.

Ouaip, et bien même en ayant déjà écrit des Quines par le passé, il m'a fallu quand même un sacré bout de temps pour trouver un programme Sense-Of-Self opérationnel ! Et j'ai mis plus de temps encore à le raccourcir. Quant à prouver que le résultat est de longueur minimale, ça je n'ai pas encore réussi. On n'aura qu'à dire que c'est à cause des médocs qui m'empêchent de me concentrer à fond.

Ah oui, avant de passer aux choses compliquées, j'ai oublié de préciser un point techneek : la longueur du code s'entend toujours relativement à un langage de programmation donné. Par exemple j'ai choisi Python vu que je sais à peu près faire que ça. Pas question donc de comparer des longueurs de code C / Python / Perl / Bash / Scala, etc.(**) De toute façon c'est le code C qui sera le plus long, tellement c'est pourri le C, beuurrrkkk.

Première tentative

Autant le dire tout de suite, cette première tentative ne fonctionne pas. Elle est là pour montrer précisément le point difficile. L'idée naïve c'est de se dire : le programme va contenir une copie de son ADN, va prendre l'entrée qu'on lui donne, comparer et afficher 0 ou 1 selon que c'est pareil ou pas. Vite fait bien fait comme ça on est direct rentré chez mémé pour aller regarder enquête d'action.

Et ben non parce que ça coince, cf. pseudo-code : If Input == ADN Then 1 Else 0. Avec la chaîne de caractère ADN qui contient une copie du programme. Ce qui donne chose comme ADN = 'If Input == ADN Then 1 Else 0'. Ah ben oui, mais maintenant la chaine 'ADN' contient aussi une copie la chaine 'ADN', c'est malin ! Du coup ça fait : ADN = 'If Input == 'If Input == ADN Then 1 Else 0' Then 1 Else 0'.

Là ça devient le Bronx, pleins de trucs ne vont pas : la nouvelle chaine contient toujours une référence à ADN, on a juste déplacé le problème d'un cran. Et surtout, de manière plus pernicieuse, se pointe une sérieuse galère avec les apostrophes : si j'utilise les mêmes apostrophes pour la première copie de ADN et la pour deuxième (et en fait pour toutes les copies ad-infinitum) on va plus savoir quelles apostrophes débutent quel ADN et quelles apostrophes terminent quel autre ADN. Merdier de ADN : tiens, je baptise ça "Syndrome de Monsanto" ça va me détendre.

Alors on la met où l'apostrophe ?

Dans ton Q ! Non lecteur adoré ce n'est pas un manque de respect. Je veux simplement indiquer qu’il faut encoder l'apostrophe dans une variable, que j’ai nommée Q comme Quote (apostrophe en anglais). Après c'est pas ma faute si en anglais le mot Quote commence par un Q et du coup ça fait un jeu de mot relou.

Foin de digressions, voici enfin la bête, Ta-Daaaaaa : 
D='Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D])';Q=chr(39);print("01"[input()=="D="+Q+D+Q+";"+D])
Ça s'utilise comme ça: 
$ cat sos.py | python3 sos.py
1
$ echo "Je suis un virus" | python3 sos.py
0

Explications

Allez, quelques explications parce que je sens des scepteeks dans le fond de la salle.

Considérons d'abord le cas où le programme se reconnait effectivement lui-même : $ python3 sos.py < sos.py répond 1. Le code lancé est contenu dans le fichier sos.py et l'entrée est aussi dans sos.py. Le programme s'exécute ainsi :

• Affecte une chaine de caractères à la variable D, comme ADN.
• Affecte chr(39) à la variable Q, comme Quote.
• Affiche le résultat d'une comparaison logeek (==) et ajoute un peu de formatage idomateek python, "01"[...] valant "0" pour False et "1" pour "True"(***).

Il faut probablement un peu de temps pour se rendre compte que le ADN du programme dépend en fait du programme lui-même (et vice-versa). C'est très précisément là que se situe la difficulté, comme avec les Quines. Dès qu'on change un iota quelque part il faut refléter ce changement ailleurs dans le programme. Mais au moins on a résolu le problème d'encodage. En effet le terme Q=chr(39) représente bien l'apostrophe mais sans l'utiliser de manière littérale.

Voyons maintenant le cas où le programme détecte autre chose que lui-même : comme précédemment, le programme reconstruit une version complète de lui-même à l'aide de son ADN et de l'apostrophe encodée (c'est la partie "D="+Q+D+Q+";"+D). Mais là il constate que cette version est différente de l'entrée (comparaison ==) et affiche finalement "0".

Reste à s'occuper de la longueur du programme : 103 symboles. Pour faire plus court, on peut déjà remarquer que les techneeks "classeeks" de code golfing ne marchent pas très bien ici : typiquement, renommer la fonction print en une fonction plus courte (mettons p) devrait être fait deux fois. Une fois dans le ADN une fois dans le programme. Il faudrait alors écrire deux fois "p=print;" ce qui consommerai en tout 16 caractères. Pas bon car au final on n’en regagne que 8 en écrivant (deux fois) p au lieu de print. J'entrevois d'autres pistes en utilisant soit la fonction eval() de python, soit l'embryon de lambda calcul intégré au langage. J’ai fait deux trois tentatives du bout des orteils, pas simple. Si on est moins regardant sur les sorties, et qu'on utilise directement "True" et "False" au lieu de "1" et "0", on tombe à 91 symboles, mais ça triche un peu par rapport à l'énoncé de départ :

D='Q=chr(39);print(input()=="D="+Q+D+Q+";"+D)';Q=chr(39);print(input()=="D="+Q+D+Q+";"+D)

Conclusion 

Il est possible d'écrire un programme court ayant "le sens-du-soi" et ne remplissant que cette fonction.

Pour ceux que les applications intéressent quand même, il n'est pas bien compliqué d'adjoindre une fonction utile au SOS de base. Par exemple pour acheter des t-shirts sur Rock A Gogo. Ce qui donne par exemple:
D='Q=chr(39);print("buy-death-metal-t-shirts");print("01"[input()=="D="+Q+D+Q+";"+D])';Q=chr(39);print("buy-death-metal-t-shirts");print("01"[input()=="D="+Q+D+Q+";"+D])
Notez que si la fonction utile contient beaucoup de symboles on peut stoker son ADN sous forme compressée. Et même, en se contentant de stoker un condensat cryptograpeek (ouais, un hash) on retombe sur une méthode connue de vérification d'intégrité du code. En fait cette méthode-là peut être trouvée plus directement sans se prendre la tête avec toutes ces histoires de sense-of-self.

Pour ceux que les applications n'excitent pas plus que ça, faites juste tourner le concept dans votre tête : il existe une machine dont l'uneek fonction est de se différencier de tout le reste.

Nan, j'déconne.

(*) Merde, parmi les gens cités il y en a qui vivent encore, et je viens de les traiter de gugusses. Alors que j'ai un infini respect pour eux.

(**) On me souffle dans l'oreillette que Kolmogorov et Chaitin avaient déjà expliqué ça genre il y a 50 ans. Désolé les gars, je vulgarise. Par contre si on pouvait arrêter de me souffler dans les oreillettes, j'ai une double otite, merci.

(***) "1" pour True, tous pour un !