Punto menos fijo

La función f ( x ) =  x ²  − 4 tiene dos puntos fijos, que se muestran como la intersección con la línea azul; su mínimo está en 1/2 −  √ 17/2 .

En la teoría del orden , una rama de las matemáticas , el punto menos fijo ( lfp o LFP , a veces también el punto fijo más pequeño ) de una función de un conjunto parcialmente ordenado ("poset" para abreviar) consigo misma es el punto fijo que es menor que cada uno. otro punto fijo, según el orden del poset. Una función no necesita tener un punto mínimo fijo, pero si lo tiene, entonces el punto mínimo fijo es único.

Ejemplos

Con el orden habitual de los números reales , el punto menos fijo de la función real f ( x ) =  x ² es x  = 0 (ya que el único otro punto fijo es 1 y 0 < 1). Por el contrario, f ( x ) =  x  + 1 no tiene ningún punto fijo, por lo que no tiene al menos uno, y f ( x ) =  x tiene infinitos puntos fijos, pero no tiene al menos uno.

Sea un grafo dirigido y sea un vértice. El conjunto de vértices accesibles desde se puede definir como el punto menos fijo de la función , definido como El conjunto de vértices que son coaccesibles desde se define por un punto mínimo fijo similar. El componente fuertemente conectado de es la intersección de esos dos puntos menos fijos. ${\displaystyle G=(V,A)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle f:\wp (V)\to \wp (V)}$ ${\displaystyle f(X)=\{v\}\cup \{x\in V:{\text{ for some }}w\in X{\text{ there is an arc from }}w{\text{ to }}x\}.}$ ${\displaystyle v}$ ${\displaystyle v}$

Sea una gramática libre de contexto . El conjunto de símbolos que produce la cadena vacía se puede obtener como el punto mínimo fijo de la función , definida como , donde denota el conjunto potencia de . ${\displaystyle G=(V,\Sigma ,R,S_{0})}$ ${\displaystyle E}$ ${\displaystyle \varepsilon }$ ${\displaystyle f:\wp (V)\to \wp (V)}$ ${\displaystyle f(X)=\{S\in V:\;S\in X{\text{ or }}(S\to \varepsilon )\in R{\text{ or }}(S\to S^{1}\dots S^{n})\in R{\text{ and }}S^{i}\in X{\text{, for all }}i\}}$ ${\displaystyle \wp (V)}$ ${\displaystyle V}$

Aplicaciones

Muchos teoremas del punto fijo producen algoritmos para localizar el punto menos fijo. Los puntos menos fijos suelen tener propiedades deseables que los puntos fijos arbitrarios no tienen.

Semántica denotacional

orden parcial en ${\displaystyle \mathbb {Z} _{\bot }}$

En informática , el enfoque de la semántica denotacional utiliza puntos mínimos fijos para obtener de un texto de programa determinado una función matemática correspondiente, llamada semántica. Para ello se introduce un objeto matemático artificial, , que denota el valor excepcional "indefinido". Dado, por ejemplo, el tipo de datos del programa , su contraparte matemática se define ya que se crea un conjunto parcialmente ordenado definiendo cada uno y permitiendo que dos miembros diferentes sean incomparables wrt , vea la imagen. ${\displaystyle \bot }$int ${\displaystyle \mathbb {Z} _{\bot }=\mathbb {Z} \cup \{\bot \};}$ ${\displaystyle \bot \sqsubset n}$ ${\displaystyle n\in \mathbb {Z} }$ ${\displaystyle n,m\in \mathbb {Z} }$ ${\displaystyle \sqsubset }$

La semántica de la definición de un programa int f(int n){...}es alguna función matemática. Si la definición del programa no termina para alguna entrada , esto se puede expresar matemáticamente como El conjunto de todas las funciones matemáticas se ordena parcialmente definiendo si, para cada una , la relación se cumple, es decir, if está menos definido o es igual a Por ejemplo, la semántica de la expresión está menos definida que la de , ya que la primera, pero no la última, se asigna a y acuerdan lo contrario. ${\displaystyle f:\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }.}$fn ${\displaystyle f(n)=\bot .}$ ${\displaystyle f\sqsubseteq g}$ ${\displaystyle n,}$ ${\displaystyle f(n)\sqsubseteq g(n)}$ ${\displaystyle f(n)}$ ${\displaystyle g(n).}$x+x/xx+1 ${\displaystyle 0}$ ${\displaystyle \bot ,}$

Dado algún texto de programa f, su contraparte matemática se obtiene como el punto mínimo fijo de algún mapeo de funciones a funciones que se puede obtener "traduciendo" f. Por ejemplo, la definición C

int hecho ( int n ) { si ( n == 0 ) devuelve 1 ; de lo contrario , devuelve n * hecho ( n -1 ); }               

se traduce a un mapeo

${\displaystyle F:(\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot })\to (\mathbb {Z} _{\bot }\to \mathbb {Z} _{\bot }),}$definido como ${\displaystyle (F(f))(n)={\begin{cases}1&{\text{if }}n=0,\\n\cdot f(n-1)&{\text{if }}n\neq \bot {\text{ and }}n\neq 0,\\\bot &{\text{if }}n=\bot .\\\end{cases}}}$

El mapeo se define de forma no recursiva, aunque se definió de forma recursiva. Bajo ciertas restricciones (ver teorema del punto fijo de Kleene ), que se cumplen en el ejemplo, necesariamente tiene un punto mínimo fijo, es decir, para todos . ^[1] Es posible demostrar que ${\displaystyle F}$fact ${\displaystyle F}$ ${\displaystyle \operatorname {fact} }$ ${\displaystyle (F(\operatorname {fact} ))(n)=\operatorname {fact} (n)}$ ${\displaystyle n\in \mathbb {Z} _{\bot }}$

${\displaystyle \operatorname {fact} (n)={\begin{cases}n!&{\text{if }}n\geq 0,\\\bot &{\text{if }}n<0{\text{ or }}n=\bot .\end{cases}}}$

Un punto fijo mayor de es, por ejemplo, la función definida por ${\displaystyle F}$ ${\displaystyle \operatorname {fact} _{0},}$

${\displaystyle \operatorname {fact} _{0}(n)={\begin{cases}n!&{\text{if }}n\geq 0,\\0&{\text{if }}n<0,\\\bot &{\text{if }}n=\bot ,\end{cases}}}$

sin embargo, esta función no refleja correctamente el comportamiento del texto del programa anterior para negativos, por ejemplo, la llamada no terminará en absoluto, y mucho menos regresará . Sólo el punto menos fijo puede utilizarse razonablemente como semántica de un programa matemático. ${\displaystyle n;}$fact(-1)0 ${\displaystyle \operatorname {fact} ,}$

Complejidad descriptiva

Immerman ^{[2] [3]} y Vardi ^[4] mostraron de forma independiente el resultado de complejidad descriptiva de que las propiedades computables en tiempo polinomial de estructuras ordenadas linealmente se pueden definir en FO(LFP) , es decir, en lógica de primer orden con un operador de punto mínimo fijo. Sin embargo, FO(LFP) es demasiado débil para expresar todas las propiedades de tiempo polinomial de estructuras desordenadas (por ejemplo, que una estructura tiene un tamaño uniforme ).

Mayores puntos fijos

El punto fijo mayor de una función se puede definir de forma análoga al punto fijo menor, como el punto fijo que es mayor que cualquier otro punto fijo, según el orden del poset. En informática , los puntos fijos mayores se utilizan con mucha menos frecuencia que los puntos mínimos fijos. Específicamente, los posets encontrados en la teoría de dominios generalmente no tienen un elemento mayor, por lo tanto, para una función dada, puede haber múltiples puntos fijos máximos mutuamente incomparables , y el punto fijo mayor de esa función puede no existir. Para abordar este problema, el punto fijo óptimo se ha definido como el punto fijo más definido compatible con todos los demás puntos fijos. El punto fijo óptimo siempre existe y es el punto fijo más grande si existe el punto fijo más grande. El punto fijo óptimo permite el estudio formal de funciones recursivas y correcursivas que no convergen con el punto menos fijo. ^[5] Desafortunadamente, mientras que el teorema de recursividad de Kleene muestra que el punto menos fijo es efectivamente computable, el punto fijo óptimo de una función computable puede ser una función no computable. ^[6]

Ver también

• Teorema de Knaster-Tarski
• Lógica de punto fijo

Notas

1. CA Gunter; DS Scott (1990). "Dominios semánticos". En Jan van Leeuwen (ed.). Modelos formales y semántica . Manual de informática teórica. vol. B. Elsevier. págs. 633–674. ISBN 0-444-88074-7.Aquí: págs. 636–638
2. N. Immerman, Consultas relacionales computables en tiempo polinómico, Información y control 68 (1–3) (1986) 86–104.
3. Immerman, Neil (1982). "Consultas relacionales computables en tiempo polinómico". STOC '82: Actas del decimocuarto simposio anual de ACM sobre teoría de la informática . págs. 147-152. doi : 10.1145/800070.802187. Versión revisada en Información y Control , 68 (1986), 86–104.
4. Vardi, Moshe Y. (1982). "La complejidad de los lenguajes de consulta relacionales". STOC '82: Actas del decimocuarto simposio anual de ACM sobre teoría de la informática . págs. 137-146. doi :10.1145/800070.802186.
5. Charguéraud, Arthur (2010). "El combinador de punto fijo óptimo" (PDF) . Demostración interactiva de teoremas . 6172 : 195–210. doi : 10.1007/978-3-642-14052-5_15 . Consultado el 30 de octubre de 2021 .
6. Shamir, Adi (octubre de 1976). Los puntos fijos de las definiciones recursivas (tesis doctoral). Instituto Weizmann de Ciencias. OCLC  884951223.Aquí: Ejemplo 12.1, págs. 12.2–3

Referencias

• Immerman, Neil . Complejidad descriptiva , 1999, Springer-Verlag.
• Libkin, Leonidas . Elementos de la teoría de modelos finitos , 2004, Springer.