¿Qué es la “continuidad” como término en el análisis computable?

Question

Fondo

Una vez implementé un tipo de datos que representa números reales arbitrarios en Haskell.Etiqueta todos los números reales teniendo una secuencia de Cauchy que converge hacia él.Eso permitirá $\mathbb{R}$ estar en la topología habitual.También implementé sumas, restas, multiplicaciones y divisiones.

Pero mi maestra dijo: "Esto no parece ser una buena idea.Dado que aquí la comparación es indecidible, esto no parece muy práctico.En particular, dejar que la división por 0 caiga en un bucle infinito no parece bueno".

Entonces quería que mi tipo de datos se extendiera $\mathbb{Q}$.Desde la comparación de igualdad de $\mathbb{Q}$ es decidible, $\mathbb{Q}$ está en topología discreta.Eso significa una topología en $\mathbb{R}$ debe ser más fino que la topología discreta en $\mathbb{Q}$.

Pero creo que descubrí que, incluso si pudiera implementar ese tipo de datos, no sería práctico.

Prueba, paso 1

Dejar $\mathbb{R}$ ser mejor que $\mathbb{Q}$ en topología discreta.Entonces $\{0\}$ está abierto en $\mathbb{R}$.Asumir $+ :\mathbb{R}^2 → \mathbb{R}$ es continuo.Entonces $\{(x,-x):x \en \mathbb{R}\}$ está abierto en $\mathbb{R}^2$.Desde $\mathbb{R}^2$ está en topología de producto, $\{(x,-x)\}$ es un elemento base de $\mathbb{R}^2$ para cada $x \en \mathbb{R}$.Resulta que $\{x\}$ es un elemento base de $\mathbb{R}$ para cada $x \en \mathbb{R}$.Eso es, $\mathbb{R}$ está en topología discreta.

Prueba, paso 2

Desde $\mathbb{R}$ está en topología discreta, $\mathbb{R}$ es computable igualdad comparable.Esto es una contradicción, entonces $+$ no es continuo, y por lo tanto no computable.

Pregunta

Lo que me molesta es el texto en negrita.Es bien sabido que toda función computable es continua (Weihrauch 2000, p.6).Aunque la definición analítica y la definición topológica de continuidad coinciden en funciones desde y hacia espacios euclidianos, $\mathbb{R}$ arriba no es un espacio euclidiano.Entonces no estoy seguro de si mi prueba es correcta.¿Cuál es la definición de "continuidad" en el análisis computable?

Answer 1

Diferentes personas tienen diferentes puntos de vista sobre cuál debería ser la definición de continuidad, pero a mi modo de ver, deberíamos definir la continuidad como computabilidad relativa a algún oráculo.Por ejemplo:

Definición:Una función $f:\mathbf{X} o \mathbf{Y}$ es continua, si hay una función parcial computable $F :\subseteq \mathbf{X} imes \mathbb{N}^\mathbb{N} o \mathbf{Y}$ y algo $p \en \mathbb{N}^\mathbb{N}$ tal que $f(x) = F(x,p)$.

Entonces, el concepto más primitivo al manejar un espacio es qué representación estamos usando para él, lo que luego produce la noción de computabilidad, y de ahí obtenemos la noción de continuidad.

Hasta ahora, la definición de continuidad parece no tener ninguna relación con la continuidad desde la topología, y uno puede preguntarse por qué se ha elegido ese término.Una razón es que normalmente utilizamos representaciones admisibles, que tienen la caracterización de que las funciones entre ellas que son continuas en la definición del análisis computable son exactamente las funciones que son continuas en el sentido topológico.

Si tenemos una representación admisible $\delta :\subseteq \Sigma^\mathbb{N} o \mathbf{X}$, obtenemos la topología $\mathbf{X}$ como la topología final a lo largo $\delta$, es decir.un conjunto $U \subseteq \mathbf{X}$ está abierto si hay un conjunto $W$ de palabras finitas tales que $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup_{w \in W} w\Sigma^\mathbb{N}$.Matthias Schröder ha demostrado que los espacios topológicos que tienen representaciones admisibles son exactamente los mismos. $T_0$ cocientes de espacios de base contable.

Ahora, volviendo lentamente al punto de partida de su pregunta, ¿qué nos impide utilizar la topología discreta en los reales?La razón por la que no podemos hacer eso es que cada espacio de base contable es separable, es decir, tiene una secuencia densa (contable).Tomar cocientes conserva ser separable, por lo que toda topología asociada a una representación es necesariamente separable.Un espacio discreto es separable si es contable, por lo que no podemos obtener la topología discreta de los reales.

Hay una manera de obtener una representación admisible de $\mathbb{R}$ lo que hace $\mathbb{Q}$ un subespacio discreto (esencialmente, tratar $\mathbb{R}$ como $\mathbb{N}^{*} aza \mathbb{N}^\mathbb{N}$), pero como usted ha argumentado en la pregunta, eso hace que la suma sea incomputable (y, en general, se parece muy poco a los reales como los querríamos).

Por cierto, no podemos evitar quedarnos atascados sin siquiera reconocerlo cuando accidentalmente intentamos dividir entre $0$ Es un obstáculo importante si intentamos hacer álgebra lineal con números reales.

Referencias:

Pieter Collins:Análisis computable con aplicaciones a sistemas dinámicos..Matemáticas.Estructura.Computadora.Ciencia.30(2):173-233 (2020)

Martín Hötzel Escardó:Topología sintética:de tipos de datos y espacios clásicos.Electrón.Notas teóricas.Computadora.Ciencia.87:21-156 (2004)

Takayuki Kihara, Arno Pauly: Dividir por cero: ¿qué tan malo es realmente?.MFCS 2016:58:1-58:14

Arno Pauly: Sobre los aspectos topológicos de la teoría de los espacios representados.Computabilidad 5(2):159-180 (2016) arXiv

Matías Schröder:Admisibilidad ampliada.Teor.Computadora.Ciencia.284(2):519-538 (2002)

Answer 2

La respuesta de Arno proporciona un material de lectura de fondo muy útil, me gustaría abordar su pregunta específica sobre $ \ mathbb {r} $ .

Primero recordemos un resultado de Peter Hertling, consulte el Teorema 4.1 en Una estructura de números real que es efectivamente categórica ( pdf aquí), sobre la estructura computable de la numeros reales. Supongamos que tenemos una representación de $ \ mathbb {r} $ , es decir, una estructura de datos que representan los reales, de manera que:

• $ 0 $ y $ 1 $ son elementos computables de $ \ mathbb {r} $ ,
• las operaciones de campo $ + $ , $ - $ , $ \ veces $ y $ / $ son computables (donde la división por cero no está definida)
• El operador de límite, tomando una secuencia cauchy rápida a su límite, es computable (una secuencia $ (x_n) _n $ es rápido cuando $ | x_n - x_m | \ leq 2 ^ {- \ min (m, n)} $ ).
• El orden estricto $ < $ es semidecidable

Las condiciones anteriores simplemente afirman que los reales deben ser un campo ordenado computable de Cauchy, que es prácticamente la versión computable de la Clasificación habitual de los reales (el axioma del Arquídean también se mantiene, como resulta).

Luego se deduce eso:

1. La topología de $ \ mathbb {r} $ es la topología de euclidean estándar
2. La igualdad es indecidible, o equivalente, testng para cero es indecidible.
3. cualquiera de estos dos estructuras son cópply isomorphic.

Estos son hechos inevitables. Su maestro puede pensar que no tener igualdad decidible es desafortunada, o que la división por parte de Zero debería informar un error, pero es imposible de organizar si uno quiere mantener la estructura computable de los reales.

Con respecto a su implementación: es vital que represente un real con una secuencia de Cauchy junto con la información sobre la rapidez convergencia. Espero que lo hicieras.