Ponto fixo, o que isso significa no mundo da ciência da computação

Eu continuo encontrando referências ao ponto fixo em perguntas e respostas no stackexchange e procuro o significado na Web, obviamente, encontrando referências em sites como o Wikipedia. No entanto, nenhuma das referências realmente responde à minha pergunta sobre o que é um ponto fixo e o que isso significa no mundo da ciência da computação.

Na ciência da computação, o uso indiscutivelmente mais proeminente de pontos fixos está na teoria da rede ¹. Uma treliça é um conjunto parcialmente ordenado $(S, \leq)$ com a propriedade adicional que fornece quaisquer dois elementos $x,y \in S$ , o conjunto $\{x,y\}$ tem um supremo e um mínimo (em $S$ ).

Agora você costuma considerar funções monótonas $f$ nessa rede que "convergem", ou seja, para alguns $x \in S$ você tem $f(x)=x$ . Resultados importantes nessa área são o teorema de ponto fixo de Kleene e o teorema de Knaster-Tarski .

Um exemplo proeminente é a treliça para A algum conjunto efef induzida por uma definição indutiva. Por exemplo, deixe A = { a , b } ∗ e definimos um idioma L ∈ 2 { a , b } ∗ por$(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}$

Esta definição indutiva corresponde à função monótona

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

Por Knaster-Tarski teorema, sabemos que tem um menor fixpoint que é um supremo de todos os "resultados intermédios" menores (o que corresponde a um número finito, muitas vezes aplicando os construtores da definição indutiva), e que menor fixpoint é certamente L .$f$$L$

A propósito, o maior ponto de fixação também tem usos; veja aqui um exemplo.

Na teoria da recursão, existe outro teorema de ponto fixo, também devido a Kleene. Ele diz ²,

Seja a numeração de Gödel ³ er : N → N uma função computável total (intuição: um compilador). Depois, há i ∈ N tal que φ r ( i ) = φ i .$\varphi$$r :\mathbb{N} \to \mathbb{N}$$i \in \mathbb{N}$$\varphi_{r(i)}=\varphi_i$

De fato, existem infinitamente muitos desses ; se houvesse apenas um número finito de pontos, poderíamos corrigir r (pela consulta da tabela) para não ter pontos fixos, contradizendo o teorema.$i$$r$

1. Todo mundo usa todos os dias, mesmo que você não perceba.
2. Eu não gosto desse artigo da Wikipedia; provavelmente é melhor verificar um livro de gênero.
3. Um tipo especial de numeração de função. Para intuição, pense nisso como uma linguagem de programação (completa em Turing).

Deixe-me elaborar um pouco a resposta de meisterluk: Imagine que estamos tentando definir a função fatorial: lembre-se da definição da função fatorial:

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

Agora, em algumas estruturas de PL (ou seja, o calcculus$\lambda$ ), não é imediatamente óbvio como definir essa função. No entanto, pode ser fácil definir a seguinte função de ordem superior, chamada porque ela assume como entrada outra função e um número natural

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

Não há uso de recursão nesta definição de função. No entanto, se houvesse alguma maneira de encontrar o ponto-fix de Fact, ou seja, uma função tal que Fact φ n = φ n para cada n , então é fácil verificar que φ é realmente uma implementação da função fatorial.$\phi$

Agora, em estruturas como o calculus, pode-se mostrar que todos os pontos fixos dessa natureza existem, de fato, o que deixa claro que você pode usá-lo como uma linguagem de programação geral.$\lambda$

Existem muitos outros usos para a noção de pontos fixos na ciência da computação, mas a maioria se resume ao que eu mostrei acima, ou seja, provar que existem certos pontos fixos para poder mostrar que certas funções ou construções estão bem definidas em sua estrutura (aqui mostramos que a função fatorial existe).

$f: A \to A$$x$$f(x)$$x$$x^2$$0$$1$$x^3$

Agora, dependendo da estrutura matemática com a qual você está lidando, existem muitas razões diferentes para se interessar por pontos fixos. Por exemplo, se você considerar um sistema dinâmico que analisa o estado do mundo e o altera (como um termostato), um ponto fixo corresponde a uma configuração estável. Se você pensa em jogos no sentido matemático da teoria dos jogos, pontos fixos correspondem a equilíbrios; se você pensa no comportamento de uma rotina de otimização que melhora iterativamente sua solução, um ponto fixo corresponde a uma solução ideal. Portanto, a noção matemática de um ponto fixo tem muitas aplicações em muitos contextos diferentes.

Uma aplicação muito comum e fundamental de pontos fixos na ciência da computação é modelar matematicamente loops e programas recursivos. Se tentarmos modelar um programa como uma função matemática, loops e recursão não serão óbvios para modelar. Isso ocorre porque o corpo de um loop é um programa e pode ser representado como uma função matemática. Como derivamos a função que representa o comportamento do loop? Corresponde à aplicação repetida do corpo do loop, em conjunto com a proteção do loop, até que nenhuma outra alteração seja possível. Da mesma forma, se modelarmos programas recursivos matematicamente, precisamos de uma noção matemática do que significa uma função se aplicar. Esta resposta é fornecida por pontos fixos.

Uma função na matemática é um mapa entre os valores de entrada e saída. Pontos fixos são valores de entrada (para uma função) que são mapeados para valores de saída que satisfazem a igualdade com a entrada.

$f(x) = x$$f(x) = x^2$$\{0, 1\}$

No que diz respeito à ciência da computação, estamos falando muito sobre funções parciais , mas isso não muda a definição de pontos fixos para nós.

Você também pode estar confuso sobre um tópico totalmente diferente: A aritmética de ponto fixo é um conceito de como representar números reais na memória. Mas o nome "pontos fixos" não se refere a esse tópico em geral (porque há apenas 1 ponto).

A teoria dos jogos é uma subárea principal do CS e um conceito importante é o equilíbrio de Nash, que é um teorema do ponto fixo. fornece um meio de identificar estratégias ótimas de jogo, uma vez que outros jogadores estão cientes das estratégias uns dos outros. pode ser comprovado pelo teorema do ponto fixo de Kakutani ou pelo teorema do ponto fixo de Brower . Nash ganhou o Prêmio Nobel de Economia em parte por desenvolver essa teoria.