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 reconnaître 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 reconnaît 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 reconnaître, 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 reconnaît 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 reconnaît 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 !
Comme toutes les offres illimitées, il y a quand même une limite en prateek. Je me doute bien que je ne peux pas stoker n’importe quel nombre de gigas, même si l’offre s’appelle "gigas illimités". Par exemple, je prends le grand nombre imaginé par XKCD, je suis certain que je ne peux pas stocker autant de gigas. En fait, ce nombre est tellement inimaginablement grand(**) que je ne peux même pas le stocker lui-même. 
