O que é “continuidade” como termo em análise computável?
fundo
Certa vez, implementei um tipo de dados que representa números reais arbitrários em Haskell. Ele rotula todos os números reais ao ter uma sequência de Cauchy convergindo para ele. Isso vai deixar$\mathbb{R}$estar na topologia usual. Eu também implementei adição, subtração, multiplicação e divisão.
Mas meu professor disse: "Isso não parece ser uma boa ideia. Como a comparação é indecidível aqui, isso não parece muito prático. Em particular, deixar a divisão por 0 cair em um loop infinito não parece bom. "
Então, eu queria que meu tipo de dados estendesse $\mathbb{Q}$. Desde comparação de igualdade de$\mathbb{Q}$ é decidível, $\mathbb{Q}$está em topologia discreta. Isso significa uma topologia em$\mathbb{R}$ deve ser mais fina do que a topologia discreta em $\mathbb{Q}$.
Mas, acho que descobri que, mesmo se eu pudesse implementar esse tipo de dados, seria impraticável.
Prova, etapa 1
Deixei $\mathbb{R}$ ser melhor do que $\mathbb{Q}$em topologia discreta. Então$\{0\}$ está aberto em $\mathbb{R}$. Presumir$+ : \mathbb{R}^2 → \mathbb{R}$é contínuo. Então$\{(x,-x): x \in \mathbb{R}\}$ está aberto em $\mathbb{R}^2$. Desde a$\mathbb{R}^2$ está na topologia do produto, $\{(x,-x)\}$ é um elemento básico de $\mathbb{R}^2$ para cada $x \in \mathbb{R}$. Segue que$\{x\}$ é um elemento básico de $\mathbb{R}$ para cada $x \in \mathbb{R}$. Isso é,$\mathbb{R}$ está em topologia discreta.
Prova, etapa 2
Desde a $\mathbb{R}$ está em topologia discreta, $\mathbb{R}$é computavelmente comparável em igualdade. Isso é uma contradição, então$+$não é contínuo e , portanto, não é computável .
Questão
O que está me incomodando é o texto em negrito. É bem sabido que toda função computável é contínua (Weihrauch 2000, p. 6). Embora a definição analítica e a definição topológica de continuidade coincidam em funções de e para os espaços euclidianos,$\mathbb{R}$acima não é um espaço euclidiano. Portanto, não tenho certeza se minha prova está correta. Qual é a definição de "continuidade" na análise computável?
Respostas
Pessoas diferentes têm visões diferentes sobre qual deve ser a definição de continuidade, mas da maneira que eu vejo, devemos definir continuidade como computabilidade em relação a algum oráculo. Por exemplo:
Definição : uma função$f : \mathbf{X} \to \mathbf{Y}$ é contínuo, se houver uma função parcial computável $F :\subseteq \mathbf{X} \times \mathbb{N}^\mathbb{N} \to \mathbf{Y}$ e alguns $p \in \mathbb{N}^\mathbb{N}$ de tal modo que $f(x) = F(x,p)$.
Portanto, o conceito mais primitivo no manuseio de um espaço é qual representação estamos usando para ele, o que então produz a noção de computabilidade, e daí obtemos a noção de continuidade.
Até agora, a definição de continuidade parece não estar relacionada à continuidade da topologia, e alguém pode se perguntar por que esse termo foi escolhido. Uma razão é que normalmente usamos representações admissíveis , que têm a caracterização de que as funções entre elas que são contínuas na definição da análise computável são exatamente as funções que são contínuas no sentido topológico.
Se tivermos uma representação admissível $\delta : \subseteq \Sigma^\mathbb{N} \to \mathbf{X}$, obtemos a topologia em $\mathbf{X}$ como a topologia final ao longo $\delta$, ou seja, um conjunto $U \subseteq \mathbf{X}$ está aberto se houver um conjunto $W$ de palavras finitas tais que $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup_{w \in W} w\Sigma^\mathbb{N}$. Matthias Schröder mostrou que os espaços topológicos que têm representações admissíveis são exatamente os$T_0$ quocientes de espaços baseados em contagem.
Agora, voltando lentamente ao ponto de partida de sua pergunta, o que nos impede de usar a topologia discreta nos reais? A razão de não podermos fazer isso é que todo espaço baseado em contagem é separável, ou seja, tem uma sequência densa (contável). Tomando quocientes preserva ser separável, então toda topologia associada a uma representação é necessariamente separável. Um espaço discreto é separável se for contável, então não podemos obter a topologia discreta em reais.
Existe uma maneira de obter uma representação admissível de $\mathbb{R}$ isto faz $\mathbb{Q}$ um subespaço discreto (essencialmente, tratar $\mathbb{R}$ Como $\mathbb{N}^{*} \cup \mathbb{N}^\mathbb{N}$), mas como você argumentou na pergunta, isso torna a adição incomputável (e, no geral, tem muito pouca semelhança com os reais como gostaríamos deles).
Por outro lado, não podemos evitar ficar presos sem nem mesmo reconhecê-lo ao tentar acidentalmente dividir por $0$ é um obstáculo significativo se estivermos tentando fazer álgebra linear com números reais.
Referências :
Pieter Collins: Análise computável com aplicativos para sistemas dinâmicos . Matemática. Struct. Comput. Sci. 30 (2): 173-233 (2020)
Martín Hötzel Escardó: Topologia Sintética: de Tipos de Dados e Espaços Clássicos . Elétron. Notas Teor. Comput. Sci. 87: 21-156 (2004)
Takayuki Kihara, Arno Pauly: Dividindo por Zero - quão ruim é, realmente? . MFCS 2016: 58: 1-58: 14
Arno Pauly: Sobre os aspectos topológicos da teoria dos espaços representados . Computabilidade 5 (2): 159-180 (2016) arXiv
Matthias Schröder: Admissibilidade alargada . Theor. Comput. Sci. 284 (2): 519-538 (2002)
A resposta de Arno fornece algum material de leitura de fundo muito útil, gostaria apenas de responder à sua pergunta específica sobre $\mathbb{R}$.
Vamos primeiro relembrar um resultado de Peter Hertling, consulte o Teorema 4.1 em Uma Estrutura de Número Real que é Efetivamente Categórico ( PDF aqui), sobre a estrutura computável dos números reais. Suponha que temos uma representação de$\mathbb{R}$, ou seja, uma estrutura de dados representando os reais, tal que:
- $0$ e $1$ são elementos computáveis de $\mathbb{R}$,
- as operações de campo $+$, $-$, $\times$ e $/$ são computáveis (onde a divisão por zero é obviamente indefinida)
- o operador de limite, levando uma sequência rápida de Cauchy ao seu limite, é computável (uma sequência $(x_n)_n$ é rápido quando $|x_n - x_m| \leq 2^{-\min(m,n)}$)
- a ordem estrita $<$ é semidecidível
As condições acima simplesmente afirmam que os reais devem ser um campo ordenado de Cauchy computável, que é praticamente a versão computável da caracterização usual dos reais (o axioma arquimediano também se mantém, como se constata).
Então, segue-se que:
- A topologia de $\mathbb{R}$ é a topologia euclidiana padrão
- A igualdade é indecidível ou, de maneira equivalente, testar o zero é indecidível.
- Quaisquer duas dessas estruturas são computavelmente isomórficas.
Esses são fatos inevitáveis. Seu professor pode pensar que não ter igualdade decidível é lamentável, ou que a divisão por zero deveria reportar um erro, mas isso é impossível de arranjar se alguém quiser manter a estrutura computável dos reais.
Quanto à sua implementação: é vital que você represente um real com uma sequência de Cauchy juntamente com informações sobre a rapidez com que converge. Eu espero que você tenha feito isso.