Point fixe, qu'est-ce que cela signifie dans le monde de l'informatique

Je continue à trouver des références à des points fixes dans les questions et réponses à stackexchange et je cherche la signification sur le Web en trouvant évidemment des références sur des sites tels que Wikipedia. Cependant, aucune des références ne répond vraiment à ma question de savoir ce qu'est un point fixe et ce que cela signifie dans le monde de l'informatique.

En informatique, l'utilisation sans doute la plus importante des points fixes se situe dans la théorie du réseau ¹. Un réseau est un ensemble partiellement ordonné avec la propriété supplémentaire que, étant donné deux éléments x , y ∈ S , l'ensemble { x , y } a à la fois un supremum et un infimum (en S ).$(S, \leq)$$x,y \in S$$\{x,y\}$$S$

Maintenant, vous considérez souvent les fonctions monotones sur ce réseau qui "convergent", c'est-à-dire que pour certains x ∈ S vous avez f ( x ) = x . Les résultats importants dans ce domaine sont le théorème du point fixe de Kleene et le théorème de Knaster-Tarski .$f$$x \in S$$f(x)=x$

Un exemple frappant est le réseau pour A un certain ensemble, et f induit par une définition inductive. Par exemple, soit A = { a , b } ∗ et nous définissons un langage L ∈ 2 { a , b } ∗ par$(2^A,\subseteq)$$A$$f$$A = \{a,b\}^*$$L \in 2^{\{a,b\}^*}$

$\qquad \begin{align} \phantom{w \in L} &\phantom{\implies} \varepsilon, a \in L \\ aw \in L &\implies baw \in L \\ bw \in L &\implies abw, bbw \in L \end{align}$

Cette définition inductive correspond à la fonction monotone

$\qquad \displaystyle f(A) = \{\varepsilon, a\} \cup A \cup \{baw \mid aw \in L\} \cup \{abw, bbw \mid bw \in L\}$

Par théorème Knaster-Tarski, nous savons que a un plus petit point fixe qui est une borne supérieure de tous les petits « résultats intermédiaires » (qui correspondent à l' application souvent les finiment constructeurs de la définition inductive), et que le plus petit point fixe est en effet L .$f$$L$

Soit dit en passant, le plus grand point fixe a également des utilisations; voir ici pour un exemple.

Dans la théorie de la récursivité, il existe un autre théorème à virgule fixe, également dû à Kleene. Il dit ²,

Soit une numérotation de Gödel ³ et r : N → N une fonction totale calculable (intuition: un compilateur). Il y a donc i ∈ N tel que φ r ( i ) = φ i .$\varphi$$r :\mathbb{N} \to \mathbb{N}$$i \in \mathbb{N}$$\varphi_{r(i)}=\varphi_i$

En fait, il existe même une infinité de tels ; s'il n'y en avait qu'un nombre fini, nous pourrions corriger r (par recherche de table) pour ne pas avoir de points fixes, contredisant le théorème.$i$$r$

1. Tout le monde l'utilise tous les jours, même si vous ne vous en rendez pas compte.
2. Je n'aime pas cet article Wikipedia; vous feriez probablement mieux de consulter un livre de genre.
3. Un type spécial de numérotation des fonctions. Pour l'intuition, considérez-le comme un langage de programmation (Turing-complet).

Permettez-moi de développer un peu la réponse de meisterluk: Imaginez que nous essayons de définir la fonction factorielle: rappelez-vous la définition de la fonction factorielle:

fact 0     = 1
fact (n+1) = n*(fact n)

Maintenant, dans certains cadres PL (à savoir le -calculus$\lambda$ ), il n'est pas immédiatement évident de définir une telle fonction. Cependant, il peut être facile de définir la fonction d' ordre supérieur suivante , ainsi appelée car elle prend en entrée une autre fonction et un nombre naturel

Fact f 0     = 1
Fact f (n+1) = n * (f n)

Il n'y a pas d'utilisation de récursivité dans cette définition de fonction. Cependant, s'il y avait un moyen de trouver le point fixe de Fact, c'est-à-dire une fonction telle que Fact ϕ n = ϕ n pour chaque n , alors il est facile de vérifier que ϕ est bien une implémentation de la fonction factorielle.$\phi$

$\lambda$

Il existe de nombreuses autres utilisations de la notion de points fixes en informatique, mais la plupart se résument à celle que j'ai montrée ci-dessus, c'est-à-dire prouver que certains points fixes existent pour pouvoir montrer que certaines fonctions ou constructions sont bien définies dans votre framework (ici nous avons montré que la fonction factorielle existe).

$f: A \to A$ est un élément $x$ Pour qui $f(x)$ est égal à $x$. Par exemple, la fonction$x^2$ a deux points fixes, qui sont les valeurs $0$ et $1$et la fonction $x^3$a trois points fixes. Mathématiquement, c'est la définition.

Now, depending on the mathematical structure you are dealing with, there are very many different reasons to be interested in fixed points. For example, if you consider a dynamic system that looks at the state of the world and changes it (like a thermostat) then a fixed point corresponds to a stable configuration. If you think of games in the mathematical sense of game theory, fixed points correspond to equillibria, if you think of the the behaviour of an optimization routine that iteratively improves its solution, a fixed point corresponds to an optimal solution. So the mathematical notion of a fixed point has a lot of applications in a lot of different contexts.

Une application très courante et fondamentale des points fixes en informatique est la modélisation mathématique de boucles et de programmes récursifs. Si nous essayons de modéliser un programme comme une fonction mathématique, les boucles et la récursivité ne sont pas évidentes à modéliser. En effet, le corps d'une boucle est un programme et peut être représenté comme une fonction mathématique. Comment dériver la fonction représentant le comportement de la boucle? Cela correspond à l'application répétée du corps de boucle, en liaison avec le protège-boucle, jusqu'à ce qu'aucun autre changement ne soit possible. De même, si nous modélisons mathématiquement des programmes récursifs, nous avons besoin d'une notion mathématique de ce que cela signifie pour une fonction de s'appliquer. Cette réponse est fournie par des points fixes.

Une fonction en mathématiques est une correspondance entre les valeurs d'entrée et de sortie. Les points fixes sont des valeurs d'entrée (pour une fonction) qui correspondent à des valeurs de sortie satisfaisant l'égalité avec l'entrée.

Pour la fonction d'égalité $f(x) = x$l'ensemble de la valeur d'entrée est égal à l'ensemble des points fixes de la fonction. Pour une fonction$f(x) = x^2$ l'ensemble des points fixes est limité à $\{0, 1\}$.

En ce qui concerne l'informatique, nous parlons beaucoup de fonctions partielles , mais cela ne change pas pour nous la définition des points fixes.

Vous pouvez également être confus sur un sujet totalement différent: l' arithmétique à virgule fixe est un concept permettant de représenter des nombres réels dans la mémoire. Mais le nom "points fixes" ne fait pas référence à ce sujet en général (car il n'y a qu'un seul point).

la théorie des jeux est une sous-zone majeure de CS et un concept important est l' équilibre de Nash qui est un théorème de point fixe. il donne un moyen d'identifier les stratégies de jeu optimales étant donné que les autres joueurs sont conscients des stratégies des autres. elle peut être prouvée via le théorème du point fixe de Kakutani ou le théorème du point fixe de Brower . Nash a remporté le prix Nobel d'économie en partie pour avoir développé cette théorie.