Itérations
J'ouvre ce fil pour traiter un thème unique. L'objectif de ce fil n'est pas d'être complet, mais d'avancer. On a créé des choses tellement artifcielles en maths que j'ai pas mal de galère à les remettre dans leur contexte naturaliste, malgré le temps que j'ai (je ne suis pas contraint par des recherches flêchées, n'étant pas payé pour). Thème unique:
L'application
$$n\longmapsto (f\mapsto f^n)$$
C'est en effet, l'opération "légitime" pour définir un entier en lambda-calcul et le LC (=TDE) donne une excellente vision naturaliste des choses.
En TDE, un entier c'est un cardinal
En LC, un entier c'est un "nombre d'itération
1/ Je rappelle les autres définitions:
d'abord une notation. $x(y)$ est l'image de $y$ par $x$, mais on a découvert qu'on peut aussi le noter $y^x$. J'utiliserai indifféremment les deux notations
1.1/ $a\times b$ est la composition, ie $(f\mapsto a(b(f)))$
1.2/ $(a+b)$ est la fonction $f\mapsto (f^a) \circ (f^b)$ que vous pouvez aussi noter comme:
$$ f\longmapsto (a(f)) \circ (b(f)) $$
Attention, pour vous être familiers, j'ai utilisé les signes usuels, mais il faut se rappeler que tout le monde a est une fonction. Par exemple le composeur
$$ x\mapsto (y \mapsto (z\mapsto x(y(z))))$$
s'applique à $x$ et donne $y\mapsto (x\circ y)$ en langue usuelle.
2/ Pourquoi ce fil?
1.4/ Force est de constater de manière de plus en plus narguante que ce que les gens appellent "artificiellement" l'exponentielle, à savoir
$$ x\mapsto (y\mapsto x(y)) $$
est juste l'identité, qui se note aussi $1$, et qui a comme propriété que $\forall x: 1(x)=x$, ce qui peut aussi s'écrire $\forall x: x^1 = x$. Or cette fonction est vécue comme un drame en maths usuelles.
De plus la programmation informatique a consacrée totalement cette procédure. Un programme c'est juste une $f$ qu'on applique $n$ soit à un uplet. Par exemple, vous obtenez la factorielle en itérant :
$$ f: (x,y) \mapsto (x\times (y+1), y+1)$$
et en partant du couple $(1,1)$. Autrement dit $fact(n+1) = ProjectionGauche(f^n( (1,1)))$
Il en va ainsi DE TOUTE FONCTION PROGRAMMABLE SUR UN ORDINATEUR. Je rappelle que "l'apparence de pouvoir donné par la programmation récursive, par exemple :
$$ f(x) := g(x,f(h(x)) ) $$
s'exécute EN VRAI dans vos PC comme suit:
begin
push x;
call h;
call f;
push x
call g
pop r
return r
end
qui n'est rien d'autre qu'une recherche du premier $n$ tel que $w^n(donnee)\in OK$ où $w$ est la fonction qui exécute un step, l'instruction push x empile x, et l'instruction pop a dépile et met la valeur dans a.
3/ Point culminant
Je crois qu'il est atteint avec ce qu'on nomme DPRM: Durant le vingtième siècle, Davis, Putman, Robinson a taffé dur pour obtenir que toute questions semi-décidable de maths se ramène de manière automatiquement à une question de la forme : $\exists u: f(u)=0$ où la lettre $u$ est pour uplet d'entiers et $f$ est une expression écrite avec les opérations uselles PLUSSSS le signe puissance.
En 1970, Matiyasevic a réussi à prouver qu'il existe un polynôme $P$ tel que $\forall (a,b,c)\in \N^3: $
$$ a=b^c\iff \exists uP(u,a,b,c)$$
démontrant ainsi que tout ensemble semi-décidable est diophantien.
Mais on retombe encore et toujours sur ce doigt d'honneur que nous adresse la fonction puissance (autrement dit, la fonction ITERER) du haut de son Olympe.
Alors attention, j'invite à rester dans le paradigme calculatoire du LC. Il n'y a que comme seule opération l'application d'un truc à un autre (c'est équivalent à la théorie des ensembles, sauf que cette dernière renvoie un truc ayant le statut phrase alors que le LC renvoie un truc ayant le statut "riendutout", c'est tout de même plus cool. même si le passage de l'un à l'autre dans les deux sens est trivial (ie $a(b)=\{x\mid (b,x) \in a\} $).
EN PARTICULIER le couple $(u,v)$ est ici la fonction
$$ f\longmapsto (f(u)(v)) $$
autrement dit, c'est "assumé" comme le "vrai" produit tensoriel de l'approche quantique, ce qui atteste de la naturalité de ce paradigme (qui arrive à "deviner" la Nature quantique du monde)
5/ Exprès, je ne donne pas les définitions usuelles de vrai et de faux, car je veux laisser des propositions affluer, éventuellement améliorantes.
L'application
$$n\longmapsto (f\mapsto f^n)$$
C'est en effet, l'opération "légitime" pour définir un entier en lambda-calcul et le LC (=TDE) donne une excellente vision naturaliste des choses.
En TDE, un entier c'est un cardinal
En LC, un entier c'est un "nombre d'itération
1/ Je rappelle les autres définitions:
d'abord une notation. $x(y)$ est l'image de $y$ par $x$, mais on a découvert qu'on peut aussi le noter $y^x$. J'utiliserai indifféremment les deux notations
1.1/ $a\times b$ est la composition, ie $(f\mapsto a(b(f)))$
1.2/ $(a+b)$ est la fonction $f\mapsto (f^a) \circ (f^b)$ que vous pouvez aussi noter comme:
$$ f\longmapsto (a(f)) \circ (b(f)) $$
Attention, pour vous être familiers, j'ai utilisé les signes usuels, mais il faut se rappeler que tout le monde a est une fonction. Par exemple le composeur
$$ x\mapsto (y \mapsto (z\mapsto x(y(z))))$$
s'applique à $x$ et donne $y\mapsto (x\circ y)$ en langue usuelle.
2/ Pourquoi ce fil?
1.4/ Force est de constater de manière de plus en plus narguante que ce que les gens appellent "artificiellement" l'exponentielle, à savoir
$$ x\mapsto (y\mapsto x(y)) $$
est juste l'identité, qui se note aussi $1$, et qui a comme propriété que $\forall x: 1(x)=x$, ce qui peut aussi s'écrire $\forall x: x^1 = x$. Or cette fonction est vécue comme un drame en maths usuelles.
De plus la programmation informatique a consacrée totalement cette procédure. Un programme c'est juste une $f$ qu'on applique $n$ soit à un uplet. Par exemple, vous obtenez la factorielle en itérant :
$$ f: (x,y) \mapsto (x\times (y+1), y+1)$$
et en partant du couple $(1,1)$. Autrement dit $fact(n+1) = ProjectionGauche(f^n( (1,1)))$
Il en va ainsi DE TOUTE FONCTION PROGRAMMABLE SUR UN ORDINATEUR. Je rappelle que "l'apparence de pouvoir donné par la programmation récursive, par exemple :
$$ f(x) := g(x,f(h(x)) ) $$
s'exécute EN VRAI dans vos PC comme suit:
begin
push x;
call h;
call f;
push x
call g
pop r
return r
end
qui n'est rien d'autre qu'une recherche du premier $n$ tel que $w^n(donnee)\in OK$ où $w$ est la fonction qui exécute un step, l'instruction push x empile x, et l'instruction pop a dépile et met la valeur dans a.
3/ Point culminant
Je crois qu'il est atteint avec ce qu'on nomme DPRM: Durant le vingtième siècle, Davis, Putman, Robinson a taffé dur pour obtenir que toute questions semi-décidable de maths se ramène de manière automatiquement à une question de la forme : $\exists u: f(u)=0$ où la lettre $u$ est pour uplet d'entiers et $f$ est une expression écrite avec les opérations uselles PLUSSSS le signe puissance.
En 1970, Matiyasevic a réussi à prouver qu'il existe un polynôme $P$ tel que $\forall (a,b,c)\in \N^3: $
$$ a=b^c\iff \exists uP(u,a,b,c)$$
démontrant ainsi que tout ensemble semi-décidable est diophantien.
Mais on retombe encore et toujours sur ce doigt d'honneur que nous adresse la fonction puissance (autrement dit, la fonction ITERER) du haut de son Olympe.
Alors attention, j'invite à rester dans le paradigme calculatoire du LC. Il n'y a que comme seule opération l'application d'un truc à un autre (c'est équivalent à la théorie des ensembles, sauf que cette dernière renvoie un truc ayant le statut phrase alors que le LC renvoie un truc ayant le statut "riendutout", c'est tout de même plus cool. même si le passage de l'un à l'autre dans les deux sens est trivial (ie $a(b)=\{x\mid (b,x) \in a\} $).
EN PARTICULIER le couple $(u,v)$ est ici la fonction
$$ f\longmapsto (f(u)(v)) $$
autrement dit, c'est "assumé" comme le "vrai" produit tensoriel de l'approche quantique, ce qui atteste de la naturalité de ce paradigme (qui arrive à "deviner" la Nature quantique du monde)
5/ Exprès, je ne donne pas les définitions usuelles de vrai et de faux, car je veux laisser des propositions affluer, éventuellement améliorantes.
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Réponses
-
L'objectif finale est bien entendu de réussir ce qu'a réussi Matiyasevic,mais contrairement à lui, de le faire sans brutalité ni inspiration.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Je profite de ce troisième post pour signaler les difficultés "défi":
1/ Pas d'égalité possible. En effet, le paradigme concerné donne un point fixe à toute fonction, donc en particulier à la fonction$ x\mapsto$ if $x=a$ then $b$ else $a$
dont un point fixe entraine $a=b$.
2/ Ca pose un problème quand il s'agit de comparer deux entiers (donnés par un nom de programme). Bin tant pis, faudra faire avec.
3/ Les maths académiques non logiciennes ont tout de même produit des simplifications pour certaines itérations célèbres, dont la plus commerciale est l'itération de:
$$ f: x\mapsto ax+b$$
usée et abusée en lycée ces dernières décennies.
Je rappelle "le trick": on prend $k$ tel que $ak=b+k$ de sorte que $\forall x: f(x)+k=a(x+k)$ et donc que
$$\forall x: f^n(x) + k = a^n(x+k)$$
4/ Comme c'est formel, ça s'applique avec les matrices
5/ Mais, je le rappelle la difficulté est qu'on n'a pas "les tests".
6/ Par exemple, DPRM serait définitivement réglé si on pouvait rendre diophantien facilement l'ensemble
$$ \{ (a,b) \mid \forall x\leq a \exists u_1\leq b\exists u_2\leq b\dots \exists u_9\leq b: P(a,x,u)=0\}$$
Mais le "=0" pose problème dans le présent paradigme. La fonction à itérer est la suivante:
$g: (x,u) \mapsto $ if $P(a,x,u) = 0$ then $(x+1,0)$ else $(x,SuccesseurDansDe(b^9)(u))$
la réponse à la question étant $\exists p: g^p(0,0) = (a,(b,b,b,\dots ,b))$?
mais le test dans sa définition est particulièrement problématique.
7/ J'en profite pour regarder vite fait une opération comme :
$$ (u,v)\mapsto (uv,v+1)$$
qui m'a servi pour produire la factorielle. Gros problème, je ne connais pas (et il n'y en pas) de matrice qui multiplie les coordonnées de son argument, comme ici. Du coup, faut que je vois pour imiter un "trick" comme en (3), comment palier à ça. Le produit scalaire le fait lui de multiplier des coordonnées mais il faut que je vois si en le regardant comme application linéaire, il serait efficace.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Une consolation quand-même.
1/ La duplication est dangereuse. C'est elle qui donne des points fixes avec:
$$ a:= [x\mapsto f(x(x))] $$
vous obtenez $a(a) = f(a(a))$. Mais vous avez dupliqué $x$, ce qui ne correspond pas à une opération qu'on peut faire dans la "vraie vie".
2/ Il y a cependant des situations où on peut simuler la duplication sans l'avoir, par exemple avec les booléens:$ f(x)(x) = [$ if $x=0$ then $f(0)(0)$ else $f(1)(1)]$
qui a l'air de dupliquer $f$, mais qui en fait ne le fait pas, via :$ f(x)(x) := $< [ if $x=0$ then $(y \mapsto y(0)(0))$ else $(z\mapsto z(1)(1))$ ] $(f) \ > $
3/ Si ces astuces vont inspirent des améliorations dans le cas des entiers, je suis preneur.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 23
+19 Invités