Formule autoréférente de Tupper — Wikipédia

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 2001^[1], il s'agit d'un exemple d'autoréférence.

Caractéristiques[modifier | modifier le code]

Définition[modifier | modifier le code]

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

${\displaystyle {1 \over 2}<\left\lfloor \mathrm {mod} \left(\left\lfloor {y \over 17}\right\rfloor 2^{-17\lfloor x\rfloor -\mathrm {mod} (\lfloor y\rfloor ,17)},2\right)\right\rfloor }$

où ${\displaystyle \lfloor \cdot \rfloor }$ est la fonction partie entière et mod l'opérateur modulo^{[1],[2],[3],[4]}.

Tracé[modifier | modifier le code]

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 suivant^[1],[5] :

Fonctionnement[modifier | modifier le code]

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é :

${\displaystyle \left\lfloor \mathrm {mod} \left(\left\lfloor {y \over 17}\right\rfloor 2^{-17\lfloor x\rfloor -\mathrm {mod} (\lfloor y\rfloor ,17)},2\right)\right\rfloor =1}$

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

${\displaystyle \left\lfloor \mathrm {mod} \left({q \over 2^{17\lfloor x\rfloor +r}},2\right)\right\rfloor =1}$

c'est-à-dire :

${\displaystyle \left\lfloor {q \over 2^{17\lfloor x\rfloor +r}}\right\rfloor }$ est impair.

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

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 2^e colonne 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[modifier | modifier le code]

Jeff Tupper publie la formule dans un article pour le SIGGRAPH 2001 (une conférence annuelle sur l'infographie), discutant des méthodes de tracés analogues à celle employée par GrafEq, un programme de représentation graphique^[1].

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

Références[modifier | modifier le code]

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tupper's self-referential formula » (voir la liste des auteurs).

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

• Récursivité
• Quine (informatique)

Liens externes[modifier | modifier le code]

• (en) « Jeff Tupper », Site officiel
• (en) « Extensions de la formule »
• (en) « Jeff Tupper's Self-Referential Formula, implemented in JavaScript. », TupperPlot
• (en) « The Library of Babel function », A Programmer's Apology
• (en) « Tupper's Formula Tools, implémenté en Javascript. »

• (fr) « Le produit de Tupper », Choux romanesco, vache qui rit et intégrales curvilignes

• Portail des mathématiques
• Portail de l’informatique