Formule autoréférente de Tupper

La formule autoréférente de Tupper est une inégalité à deux variables. Lorsque l'ensemble des points du plan qui satisfont cette inégalité sont tracés, une partie du plan représente la formule elle-même. Créée par Jeff Tupper en Modèle:Date, il s'agit d'un exemple d'autoréférence.

Caractéristiques

Définition

La formule est une inégalité définie par :

$\frac{1}{2}<\lfloor \mathrm{m}\mathrm{o}\mathrm{d}(\lfloor \frac{y}{17}\rfloor 2^{-17\lfloor x\rfloor -\mathrm{m}\mathrm{o}\mathrm{d}(\lfloor y\rfloor ,17)},2)\rfloor$

où $\lfloor \cdot \rfloor$ est la fonction partie entière et mod l'opérateur moduloModèle:,Modèle:,Modèle:,.

Tracé

Soit k le nombre de 543 chiffres égal à :

960939379918958884971672962127852754715004339660129306651505519271702802395266

424689642842174350718121267153782770623355993237280874144307891325963941337723

487857735749823926629715517173716995165232890538221612403238855866184013235585

136048828693337902491454229288667081096184496091705183454067827731551705405381

627380967602565625016981482083418783163849115590225610003652351370343874461848

378737238198224849863465033159410054974700593138339226497249461751545728366702

369745461014655997933798537483143786841806593422227898388722980000748404719

Si on trace le graphe de l'ensemble des points (x,y) qui satisfont l'inégalité de Tupper sur la restriction du plan à 0 < x < 106 et k < y < k+17, on obtient le graphe suivantModèle:, :

Tracé de l'inégalité de Tupper sur [0;106]×[k;k+17] ; par simplicité, le tracé a été ramené verticalement au niveau de y=0.

Fonctionnement

Du fait de la partie entière et du modulo 2, la partie droite de l'inégalité ne peut prendre comme valeur que 0 ou 1. Les solutions de l'inégalité sont donc celles de l'égalité :

$\lfloor \mathrm{m}\mathrm{o}\mathrm{d}(\lfloor \frac{y}{17}\rfloor 2^{-17\lfloor x\rfloor -\mathrm{m}\mathrm{o}\mathrm{d}(\lfloor y\rfloor ,17)},2)\rfloor =1$

On pose q le quotient de la division euclidienne de $\lfloor y\rfloor$ par 17 et r son reste : $q=\lfloor \frac{y}{17}\rfloor$ et $r=\mathrm{m}\mathrm{o}\mathrm{d}(\lfloor y\rfloor ,17)$. On peut écrire : $\lfloor y\rfloor =17q+r$. L'équation précédente devient (en divisant par la puissance de 2 plutôt qu'en multipliant par son opposé) :

$\lfloor \mathrm{m}\mathrm{o}\mathrm{d}(\frac{q}{2^{17\lfloor x\rfloor +r}},2)\rfloor =1$

c'est-à-dire :

$\lfloor \frac{q}{2^{17\lfloor x\rfloor +r}}\rfloor$ est impair.

Dans cette formule, la partie entière de la division de q par $2^{17\lfloor x\rfloor +r}$ permet d'obtenir le $17\lfloor x\rfloor +r$-ième bit de q.

De façon générale, la formule de Tupper décode une image matricielle monochrome stockée dans une constante q. Le bit de poids faible de q encode le pixel du coin inférieur gauche de l'image, les 17 premiers bits de poids faibles encodent la colonne de pixels la plus à gauche, les 17 bits suivants encodent la Modèle:2e la plus à gauche, ainsi de suite.

Lorsqu'elle est appliquée à tous les nombres y positifs, l'inégalité trace une bande verticale contenant toutes les images possibles de 17 pixels de hauteur. La tranche située entre k et k+17 décrit la formule elle-même, mais ce n'est qu'un cas particulier : toutes les autres formules possibles sont également décrites ailleurs, pour peu qu'elles tiennent sur 17 pixels de hauteur.

Historique

Jeff Tupper publie la formule dans un article pour le SIGGRAPH Modèle:Date (une conférence annuelle sur l'infographie), discutant des méthodes de tracés analogues à celle employée par Modèle:Lien, un programme de représentation graphique.

Tupper a composé depuis des versions étendues de sa formule originale, qui excluent tout le plan sauf une zone particulière.

Annexes

Articles connexes

• Récursivité
• Quine (informatique)

Liens externes

• Modèle:Lien web
• Modèle:Lien web
• Modèle:Lien web
• Modèle:Lien web
• Modèle:Lien web