Encodage des entiers

Petite réaction suite au visionnage d'une vidéo et de ses commentaire traitant de 1+1=0. Comme quoi on peut traiter de sujet intéressant même en partant d'une chose simple.

La vidéo traite de l'encodage du binaire et de l’opérateur addition sur les binaires en passant forcement par l’équivalence entre décimal et binaire. En lisant les commentaires, j'ai vu beaucoup de gens discourir sur l’opération d'addition en elle même dans le cadre informatique.

Pourtant, il me semble qu'il ne faut pas confondre implémentation numérique et le concept mathématique représenté. Ici bien que l'exemple soit traité via un outil ce qui nous donne envie de traiter la question comme d'un problème d'algorithmie logiciel, la notion de codage binaire n'a pas besoin de limite ainsi 1+1 = 10 en binaire et c'est toujours vrai, après si on implémente cet opération avec des boolean (dans n'importe quel langage), forcement 1+1=0 alors que si on l'implémente avec des bytes, alors on aura 10. Il ne faut pas oublier la différence entre l'aspect conceptuel et son implémentation.

En fait cela m’amène a une réflexion sur les équivalences d'encodage et pourquoi utiliser l'un plutôt qu'une autre (on en revient a un problème de modélisation non?) Ainsi je résumerai la première partie de la vidéo de Bruce par:
zero       0    0
un          1    1
deux      2    10
trois       3    11
quatre    4    100
cinq       5    101
six         6    110 

C'est trois représentations sont équivalent des concepts mathématique associés (les valeurs de [0-6]) mais leur représentation syntaxique est différente et ne permettent pas les même choses car implémenter logiciellement une opération telle que l'addition sur un binaire sera plus évident que sur du décimal qui est plus simple que sur du lexical.... (d’ailleurs l'utilisation des porte logique le montre, faire quelque chose d’équivalent avec des "un" et des "deux" sera vraiment un challenge)

Mais on aurai aussi pu faire une représentation du type fonctionnel en utilisant les entiers de Peano [2]: au lieu d'encoder en binaire et de définir un opérateur tel que le +, avec Peano, on défini juste 0 comme point initial ( celui ci peut être définit comme l’équivalent de 0 mais on peut aussi le donner comme équivalent de 100 -> ceci s’appelle définir la sémantique mais c'est un autre problème et ça n'a d'importance que si on veut "traduire" la logique) et on définit l’opérateur SUCC représentant le suivant. Du coup pour faire comme dans le tableau précédent, on aura:

0  -> 0
1 -> SUCC(0)
2 -> SUCC(SUCC(0))
3 -> SUCC(SUCC(SUCC(0)))
4 -> SUCC(SUCC(SUCC(SUCC(0))
5 -> SUCC(SUCC(SUCC(SUCC(SUCC(0))

Avec ça on a aussi une représentation des entiers (ou encodage) n'utilisant qu'un seul symbole "0" et un opérateur...
Après si vous voulez rajouter des opérateur classique comme + alors il faut revoir implémentation qui la est fort simple car il suffit de combiner le nombre de SUCC de l'un avec l'autre (ou les concatener....)

Exemple:

SUCC(SUCC(0)) +SUCC(SUCC(0)) = SUCC(SUCC(SUCC(SUCC(0))

Bon je suis peut être parti un peu loin

Références:

[1] https://www.youtube.com/watch?v=i4jSXR4swrY&index=390&list=WL
[2] http://www.fil.univ-lille1.fr/~wegrzyno/portail/Elfe/Doc/TPPL3/tp3002.html