Punto mínimo fijo

Punto fijo más pequeño de una función de un conjunto parcial

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

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

Ejemplos

Con el orden habitual de los números reales , el punto fijo mínimo 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 ningún mínimo, y f ( x ) =  x tiene infinitos puntos fijos, pero no tiene ningún mínimo.

Sea un grafo dirigido y un vértice. El conjunto de vértices accesibles desde se puede definir como el mínimo punto fijo de la función , definida como El conjunto de vértices que son coaccesibles desde se define por un mínimo punto fijo similar. El componente fuertemente conexo de es la intersección de esos dos mínimos puntos 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 fijo mínimo 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 de 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 los puntos mínimos fijos para obtener de un texto de programa dado una función matemática correspondiente, llamada su 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 , se define su contraparte matemática, ya que se convierte en un conjunto parcialmente ordenado definiendo para cada uno y permitiendo que dos miembros diferentes sean incomparables con respecto a , consulte 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 una definición de 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 la relación se cumple, es decir, si es menos definida o 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 concuerdan de 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 un texto de programa f, su contraparte matemática se obtiene como el punto mínimo fijo de alguna aplicación de funciones a funciones que se puede obtener mediante "traducción" f. Por ejemplo, la definición de C

int fact ( int n ) { si ( n == 0 ) devuelve 1 ; de lo contrario devuelve n * fact ( 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}}}$

La aplicación se define de forma no recursiva, aunque se definió recursivamente. Bajo ciertas restricciones (ver el teorema del punto fijo de Kleene ), que se cumplen en el ejemplo, necesariamente tiene un punto fijo mínimo, , es decir para todo . ^[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 valores negativos, por ejemplo, la llamada no terminará en absoluto, y mucho menos retornará . Solo el punto menos fijo puede usarse razonablemente como una semántica de programa matemático. ${\displaystyle n;}$fact(-1)0 ${\displaystyle \operatorname {fact} ,}$

Complejidad descriptiva

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

Puntos fijos más grandes

El punto fijo máximo de una función se puede definir de forma análoga al punto fijo mínimo, como el punto fijo que es mayor que cualquier otro punto fijo, según el orden del conjunto parcial. En informática , los puntos fijos máximos se utilizan con mucha menos frecuencia que los puntos fijos mínimos. En concreto, los conjuntos parciales que se encuentran en la teoría de dominios normalmente no tienen un elemento máximo, por lo que para una función dada, puede haber múltiples puntos fijos máximos mutuamente incomparables , y el punto fijo máximo de esa función puede no existir. Para abordar esta cuestión, 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áximo si existe el punto fijo máximo. El punto fijo óptimo permite el estudio formal de funciones recursivas y correcursivas que no convergen con el punto fijo mínimo. ^[5] Desafortunadamente, mientras que el teorema de recursión de Kleene muestra que el punto fijo mínimo es efectivamente computable, el punto fijo óptimo de una función computable puede ser una función no computable. ^[6]

Véase 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 polinomial, Información y Control 68 (1–3) (1986) 86–104.
3. Immerman, Neil (1982). "Consultas relacionales computables en tiempo polinomial". STOC '82: Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación . 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 la ACM sobre teoría de la computación . págs. 137–146. doi :10.1145/800070.802186.
5. Charguéraud, Arthur (2010). "El Combinador Óptimo de Punto Fijo" (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, Leonid . Elementos de la teoría de modelos finitos , 2004, Springer.