Interprétation physique
Bonjour,
je cherche depuis assez longtemps une interprétation (et peut-être une application) en "physique" d'un résultat d'informatique théorique qui énonce que pour toute application $F:\{0,1\}^n\to\{0,1\}^n$, il existe un entier $k$ et une séquence suite finie $(i_1,f_1),(i_2,f_2),\dots (i_k,f_k)$ avec les $i$ dans $[1,n]$ et les $f:\{0,1\}^n\to\{0,1\}$ tels que la séquence de calcul $x_{i_1}:=f_1(x),v x_{i_2}:=f_2(x),\ldots,\ x_{i_k}:=f_k(x)$ transforme tout vecteur $x$ de $\{0,1\}^n$ en son image $F(x)$. On a même $k\le 4n-3$.
Ceci se généralise à tout ensemble fini $S$ autre que $\{0,1\}$ et aussi à $S=\N$ où on aura même $k\le n+1$
Cela implique par exemple qu'une opération modifiant des registres d'un processeur en fonction de leurs valeurs peut se réaliser par une séquence d'opérations portant sur ces registres sans avoir besoin de mémoire auxiliaire.
L'exemple classique est l'échange de valeurs. Pour échanger les valeurs de deux registres $A,\ B$, on le fait habituellement en utilisant un troisième registre $C$ par $C:=A, A:=B, B:=C$.
Mais le théorème dit qu'on peut s'en passer. En effet, on peut faire $A:=A\oplus B,\ B:=A\oplus B,\ A:=A\oplus B$, où $\oplus$ est le XOR (ou exclusif, addition modulo 2) bit à bit.
La vague intuition physique que je me fais est qu'un système physique peut donc évoluer "itérativement" sans nécessiter de "copier de l'information"... C'est thermodynamique ? Une autre intuition est cette possibilité d'effectuer une transformation "globale" par une séquence d'opérations "locales"... C'est relativiste ?
Merci pour vos interprétations ...
je cherche depuis assez longtemps une interprétation (et peut-être une application) en "physique" d'un résultat d'informatique théorique qui énonce que pour toute application $F:\{0,1\}^n\to\{0,1\}^n$, il existe un entier $k$ et une séquence suite finie $(i_1,f_1),(i_2,f_2),\dots (i_k,f_k)$ avec les $i$ dans $[1,n]$ et les $f:\{0,1\}^n\to\{0,1\}$ tels que la séquence de calcul $x_{i_1}:=f_1(x),v x_{i_2}:=f_2(x),\ldots,\ x_{i_k}:=f_k(x)$ transforme tout vecteur $x$ de $\{0,1\}^n$ en son image $F(x)$. On a même $k\le 4n-3$.
Ceci se généralise à tout ensemble fini $S$ autre que $\{0,1\}$ et aussi à $S=\N$ où on aura même $k\le n+1$
Cela implique par exemple qu'une opération modifiant des registres d'un processeur en fonction de leurs valeurs peut se réaliser par une séquence d'opérations portant sur ces registres sans avoir besoin de mémoire auxiliaire.
L'exemple classique est l'échange de valeurs. Pour échanger les valeurs de deux registres $A,\ B$, on le fait habituellement en utilisant un troisième registre $C$ par $C:=A, A:=B, B:=C$.
Mais le théorème dit qu'on peut s'en passer. En effet, on peut faire $A:=A\oplus B,\ B:=A\oplus B,\ A:=A\oplus B$, où $\oplus$ est le XOR (ou exclusif, addition modulo 2) bit à bit.
La vague intuition physique que je me fais est qu'un système physique peut donc évoluer "itérativement" sans nécessiter de "copier de l'information"... C'est thermodynamique ? Une autre intuition est cette possibilité d'effectuer une transformation "globale" par une séquence d'opérations "locales"... C'est relativiste ?
Merci pour vos interprétations ...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Voici un énoncé "technique" d'un résultat assez contre-intuitif.
L'idée est qu'un système peut évoluer sans avoir à copier de l'information ailleurs comme par exemple pour stocker des parties transitoires de ses états.
Pour tout $n$ et toute application $F:\{0,1\}^n\mapsto\{0,1\}^n$, il existe un entier $k$ et une séquence finie $(i_1,f_1),(i_2,f_2),\dots (i_k,f_k)$ avec les $i$ dans $[1,n]$ et les $f:\{0,1\}^n\mapsto\{0,1\}$ tels que la séquence de calcul $x_{i_1}:=f_1(x)$, $x_{i_2}:=f_2(x)$,...,$x_{i_k}:=f_k(x)$
transforme tout vecteur $x$ de $\{0,1\}^n$ en son image $F(x)$. On a même $k\le 4n-3$.
Ceci se généralise à tout ensemble fini $S$ autre que $\{0,1\}$ et aussi à $S=\N$ où on aura même $k\le n+1$
Cela implique par exemple qu'une opération modifiant des registres d'un processeur en fonction de leurs valeurs peut se réaliser par une séquence d'opérations sur ces registres sans recourir à d'autres registres ou de la mémoire auxiliaire.
L'exemple classique que je donne pour illustrer cela est l'échange de valeurs. Pour échanger les valeurs de deux registres $A,B$, on le fait habituellement en utilisant un troisième registre $C$ par $C:=A, A:=B, B:=C$.
Mais le théorème dit qu'on peut s'en passer. En effet, on peut faire $A:=A\oplus B,B:=A\oplus B,A:=A\oplus B$
où $\oplus$ est le XOR (ou exclusif, addition modulo 2) bit à bit.
Notez que comme pour cet échange, si l'application $F$ est linéaire, alors on a $k\le 2n-1$.
Je cherche une interprétation physique de ces résultats (s'il y en a une...peut-être en thermodynamique ?).
Merci pour vos interprétations....
EDIT : ah ok à chaque étape $j\leq k$ tu réaffectes $x_{i_j}$ en $f_j(x)$, c'est ça ?
On veut obtenir la valeur $y=F(x)$.
La valeur initiale est le $x$ de départ, puis on modifie $x_{i_1}$ puis $x_{i_2}$ etc....et on arrive à $x=y$.
En maths, on se fiche de savoir comment on calcule $F(x)$. En informatique, cela se fait par étapes....au moins si la structure est "trop grosse" (disons aujourd'hui au delà des 64 bits).
Idem pour une Machine de Turing...on peut écrire une lettre (ou un mot fini borné) dans une case.
EDIT sur ton EDIT : yes, that's it !
Physiquement, je n'en vois pas d'interprétation simple. En TQ tout est réversible donc pas concernée et en classique tout est continu..
justement au sujet de "TQ" et la réversibilité, pour les applications bijectives, le calcul se fait en $2n-1$ étapes et les effectuer en sens inverse calcule l'application inverse. Je n'ai rien dit sur les indices. Ils sont successifs. Ainsi pour les bijections ou les applications linéaires, les indices sont : $$1,2,...,n-1,n,n-1,...2,1$$
Voici une preuve sale de l'énoncé.
Soit $F$ la plus petite possible contre-exemple. Soit $s$ le plus grand élément de son image directe. Il n'est pas nul. On le remplace par $s'<s$ en changeant 1 bit (le 17 par exemple) en 0. Et on remplace $F$ par $G$ où les images de tous les antécédents de $s$ par $F$ sont envoyés sur $s'$. Comme $G<F$, elle n'est pas un contre-exemple, et il suffit donc, pour calculer $F(x)$ avec les contraintes que tu dis d'ajouter juste l'opération [ if $x=s'$ then $s$ else $x$ ] une fois avoir calculé $G(x)$.
Cette preuve donne un $k$ monstrueux :-D
c'est en effet ce genre de "trucs" que l'on utilise...mais c'est plus compliqué dans le cas fini. Pour $\N$ c'est assez simple et dans ce style.
Dans ce que tu dis, tu poses la définition pour $s'<_{lex} s$ :
$$G(x)=\cases{s'&si $F(x)=s$\cr
F(x)&sinon}$$
C'est ça ? Donc on a l'implication $(F(x)=s)\implies (G(x)=s')$.
Mais ce n'est pas une équivalence. Il peut y avoir de "vrais" $y$ pour lesquels $F(y)=s'$ et ils seront envoyés sur $s$ par ton procédé...non ?
Je veux dire, pourquoi $F^{-1}(s')$ serait vide ?
L'heure est à aller au dodo...
Mais ça ne me borne pas K linéairement comme tu l'annonces.
Evidemment, je n'ai pas les bornes optimisées (ni cherché à les obtenir).
Soit $n$ un entier et pour chaque $F: 2^n\to 2^n$; posons $\phi(F):=(u,v)$ le couple de nombre entiers obtenu suit:
$u:=card(2^n-Im(F))$
$v:= $ if $F$ n'est pas bijective then $0$ else plus petit nombre de transpositions de $S(2^n)$ permettant d'obtenir $F$.
Soit $(u,v)$ le plus petit couple d'un contre-exemple à son énoncé. Si $u\neq 0$, on remplace, en changeant l'image d'un seul élément $F$ par une $G$ dont le $u$ est plus petit. La suite est facile
Si $u=0$, c'est que $F$ est une bijection. On la compose à gauche par une translation qui fait diminuer son $v$ et la suite est facile.
Je n'ai pas contre aucune idée de comment fait Serge pour obtenir ses bornes optimistes.
Mais c'est en effet la 1ère approche que j'avais eu pour montrer l'existence de ce type de calcul.
Dans tous les cas, il faut un peu de théorie des graphes et éventuellement un peu d'arithmétique.
Tu peux regarder mon premier papier sur le sujet...mais j'ai comme l'impression que tu préfères trouver par toi-même.
https://www.sciencedirect.com/science/article/pii/0304397595001719
Merciiii je regarderai. Et non, je n'ai pas de préférence, mais suis peu dispo.
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00959964/document
Une question reste ouverte : je pense qu'on peut descendre à $3n-2$ mais sans fixer d'ordre sur les indices.