Opération complète
Bonjour,
Je voudrais vous proposer une opération qui pourrait s'avérer utile. Une opération unique qui permet par composition de produire toutes les fonctions de $\{0,1,\ldots,n-1\}^k$ dans $\{0,1,\ldots,n-1\}$ pour tous les $n\ge 2$ et tous les $k>0$.
C'est une sorte de généralisation de l'opération logique NOR qui est bien connue pour être complète dans le cas booléen $n=2$.
L'opération suivante $\phi$ de $\N^3$ dans $\N$ généralise cela et engendre par composition toutes les fonctions :
$$
\phi(x,y,z)=\cases{x+1&si $x=y\le z$\cr
0&sinon}
$$ Par exemple, la fonction constante nulle est définissable par $\phi(\phi(x,x,x),x,x)$. En effet, cela vaut $\phi(x+1,x,x)=0$.
Les preuves et les détails sont donnés dans l'article ci-joint.
J'ai ressorti cela de mes cartons pour autre chose. Peut-être que cela pourra servir à quelqu'un ici. Par exemple, quand on veut montrer une propriété sur toutes les fonctions, il suffit de la vérifier sur l'identité et que $\phi$ la préserve.
Je voudrais vous proposer une opération qui pourrait s'avérer utile. Une opération unique qui permet par composition de produire toutes les fonctions de $\{0,1,\ldots,n-1\}^k$ dans $\{0,1,\ldots,n-1\}$ pour tous les $n\ge 2$ et tous les $k>0$.
C'est une sorte de généralisation de l'opération logique NOR qui est bien connue pour être complète dans le cas booléen $n=2$.
L'opération suivante $\phi$ de $\N^3$ dans $\N$ généralise cela et engendre par composition toutes les fonctions :
$$
\phi(x,y,z)=\cases{x+1&si $x=y\le z$\cr
0&sinon}
$$ Par exemple, la fonction constante nulle est définissable par $\phi(\phi(x,x,x),x,x)$. En effet, cela vaut $\phi(x+1,x,x)=0$.
Les preuves et les détails sont donnés dans l'article ci-joint.
J'ai ressorti cela de mes cartons pour autre chose. Peut-être que cela pourra servir à quelqu'un ici. Par exemple, quand on veut montrer une propriété sur toutes les fonctions, il suffit de la vérifier sur l'identité et que $\phi$ la préserve.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses