O que é a "continuidade" como um termo em computável análise?

Question

Fundo

Eu uma vez implementado um tipo de dados que representa arbitrária de números reais em Haskell.Ele rótulos de todos os números reais, por ter uma sequência de Cauchy converge para ele.Que vai deixar $\mathbb{R}$ estar na topologia usual.Eu também implementada a adição, a subtração, a multiplicação e a divisão.

Mas meu professor disse, "Esta não parece ser uma boa idéia.Desde comparação é indecidíveis aqui, isso não parece muito prático.Em particular, permitindo a divisão por 0 a cair em um loop infinito não parece bom."

Então, eu queria que o meu tipo de dados para ampliar $\mathbb{Q}$.Desde a comparação de igualdade de $\mathbb{Q}$ é decidível, $\mathbb{Q}$ é na topologia discreta.Isso significa que uma topologia em $\mathbb{R}$ deve ser mais fina que a topologia discreta em $\mathbb{Q}$.

Mas, eu acho que eu descobri que, mesmo se eu pudesse implementar esse tipo de dados, será impraticável.

Prova da etapa 1

Deixe $\mathbb{R}$ ser mais fino do que $\mathbb{Q}$ na topologia discreta.Em seguida, $\{0\}$ é aberto no $\mathbb{R}$.Suponha $+ :\mathbb{R}^2 → \mathbb{R}$ é contínuo.Em seguida, $\{(x,-x):x \in \mathbb{R}\}$ é aberto no $\mathbb{R}^2$.Desde $\mathbb{R}^2$ é no produto de topologia, $\{(x,-x)\}$ é um elemento de base $\mathbb{R}^2$ para cada $x \in \mathbb{R}$.Segue-se que $\{x\}$ é um elemento de base $\mathbb{R}$ para cada $x \in \mathbb{R}$.Que é, $\mathbb{R}$ é na topologia discreta.

Prova da etapa 2

Desde $\mathbb{R}$ é na topologia discreta, $\mathbb{R}$ é computably igualdade comparáveis.Isso é uma contradição, então $+$ não é contínua, e, assim, não computáveis.

Pergunta

O que está me incomodando é o texto em negrito.É bem sabido que cada computável função é contínua (Weihrauch 2000, p.6).Embora a análise e definição topológica definição de continuidade coincidem em funções de e para Euclidiana espaços, $\mathbb{R}$ acima não é um espaço Euclidiano.Então, eu não tenho certeza se a minha prova está correta.Qual é a definição de "continuidade" no computável análise?

Answer 1

Diferentes pessoas têm diferentes pontos de vista sobre o que a definição de continuidade deve ser, mas a minha maneira de ver, devemos definir a continuidade para ser computability em relação a alguns oracle.Por exemplo:

Definição:Uma função $f :\mathbf{X} o \mathbf{Y}$ é contínua, se existir uma função parcial computável $F :\subseteq \mathbf{X} imes \mathbb{N}^\mathbb{N} o \mathbf{Y}$ e alguns $p \in \mathbb{N}^\mathbb{N}$ de tal forma que $f(x) = F(x,p)$.

Assim, o mais primitivo conceito em tratamento de um espaço é que a representação que estamos usando para ele, que, em seguida, gera a noção de computability, e de que nós temos a noção de continuidade.

Até agora, a definição de continuidade parece bastante relacionada à continuidade da topologia, e pode-se perguntar por que o termo tenha sido escolhido.Uma razão é que nós usamos geralmente o admissível representações, que têm a caracterização de que as funções entre eles, que são contínuas em a computável análise de definição são exatamente as funções que são contínuos no sentido topológico.

Se temos uma admissível a representação $\delta :\subseteq \Sigma^\mathbb{N} o \mathbf{X}$, temos a topologia em $\mathbf{X}$ como o final de topologia ao longo $\delta$, i.é.um conjunto de $U \subseteq \mathbf{X}$ está aberto iff há um conjunto $W$ do finito de palavras tais que $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup_{w \W} w\Sigma^\mathbb{N}$.Matthias Schröder tem mostrado que o topológica espaços que têm admissível representações são exatamente os $T_0$ quocientes de countably baseado espaços.

Agora, lentamente, voltar para o ponto de partida de sua pergunta, o que nos impede de usar a topologia discreta sobre as reais?A razão para que não o fazer é que cada countably baseado no espaço é separável, ou seja, tem um (contável) denso em sequência.Tendo quocientes preserva sendo separáveis, de modo que cada topologia associada a uma representação é necessariamente inseparáveis.Uma discreta espaço é separável iff é contável, então podemos chegar a topologia discreta sobre as reais.

Existe uma maneira de obter uma admissível a representação de $\mathbb{R}$ que faz $\mathbb{Q}$ uma discreta subespaço (essencialmente, tratar $\mathbb{R}$ como $\mathbb{N}^{*} \cup \mathbb{N}^\mathbb{N}$), mas como você tem argumentado em questão, que faz além de uncomputable (e, em geral, tem muito pouca semelhança com as reais como nós queremos).

Em uma nota de lado, que não podemos evitar ficar preso mesmo sem reconhecer quando acidentalmente tentar dividir por $0$ é um obstáculo significativo se estamos tentando fazer álgebra linear com números reais.

Referências:

Pieter Collins:Computável análise com aplicações para sistemas dinâmicos.Matemática.Struct.Transf.Sci.30(2):173-233 (2020)

Martín Hotzel Escardó:Sintético De Topologia:de Tipos de Dados e Clássica Espaços.Elétron.Notas Oou.Transf.Sci.87:21-156 (2004)

Takayuki R.b., Arno Pauly: Divisão por Zero - Como é Que É Ruim, Realmente?.MFCS 2016:58:1-58:14

Arno Pauly: No topológica aspectos da teoria dos espaços representados.Computability 5(2):159-180 (2016) arXiv

Matthias Schröder:Prorrogado de admissibilidade.Oou.Transf.Sci.284(2):519-538 (2002)

Answer 2

Arno resposta fornece alguns muito úteis fundo material de leitura, eu apenas gostaria de abordar a sua pergunta específica sobre o $\mathbb{R}$.

Vamos recordar um resultado por Peter Hertling, ver Teorema 4.1 na Um Número Real Estrutura que Efetivamente é Categórica (PDF aqui), sobre computável estrutura dos números reais.Suponha que temos uma representação de $\mathbb{R}$, i.é., uma estrutura de dados que representa as reais, tais que:

• $0$ e $1$ são computáveis elementos de $\mathbb{R}$,
• as operações de campo $+$, $-$, $ imes$ e $/$ são computáveis (onde a divisão por zero é, claro, indefinido)
• o limite do operador, levando a uma rápida sequência 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 estrita ordem $<$ é semidecidable

As condições acima, simplesmente, que o estado de reais deve ser um computável de Cauchy ordenou campo, que é praticamente o computáveis versão do habitual chracterization de reais (o axioma de Arquimedes considera tão bem, como se vê).

Em seguida, segue que:

1. A topologia de $\mathbb{R}$ é a norma Euclidiana de topologia
2. A igualdade é indecidíveis, ou equivalentemente, testng para zero é indecidíveis.
3. Quaisquer duas dessas estruturas são computably isomórficas.

Estas são inevitáveis fatos.O professor pode pensar que não ter decidível igualdade é infeliz, ou que a divisão por zero deve relatar um erro, mas que é impossível organizar se se quer manter a computável estrutura de reais.

A respeito de sua implementação:é vital que você representa um real com uma sequência de Cauchy em conjunto com informações sobre o quão rápido ele converge.Eu espero que você fez isso.