¿El término "continuidad" tiene un significado diferente en las matemáticas y en el CS?

Question

Hago esta pregunta porque de algunas declaraciones en la pregunta "¿Qué es la "continuidad" como un término en computables análisis?" me hace sospechoso.

Yo soy ingeniero, no científico de la computación, así que no tengo la máquina de Turing, pero las puertas de la lógica en la mente cuando pienso en operaciones algebraicas realizadas con los dispositivos.

He leído la respuesta a la pregunta "¿Por qué son funciones computables continua?" y se entiende de la siguiente manera:

Debido a que el dispositivo de entrada es de longitud infinita (un número decimal con un número infinito de dígitos después del punto decimal), el dispositivo (por ejemplo,Máquina de Turing o equipo) no se puede leer el número completo antes de escribir la $n$-ésimo dígito de salida.

En su lugar, el dispositivo sólo puede haber leído $m(n)$ los dígitos de la entrada cuando se escribe la $n$-ésimo dígito de salida.

Si el primer $n$ los dígitos de la salida de función que depende sólo de la primera $m(n)$ los dígitos de la entrada, la función es continua.

Sin embargo, si entiendo esta argumentación correctamente, la palabra "continuo" en el cálculo de la teoría no es idéntica a la palabra "continuo" en matemáticas:

Redondeo hacia cero requeriría solamente la lectura de la entrada hasta que el punto decimal (por lo $m(n)= ext{const.}$);sin embargo, la función matemática que se calcula no es "continuo", según la definición matemática de ese término.

También podríamos realizar un dígito sabio operación ($m(n)=n$) y el intercambio de ciertos dígitos después del punto decimal;por ejemplo reemplazar todos 4s por 9y todos los 9s por 4s.Como tengo entendido, la función que se calcula no es continua en cualquier intervalo de $\mathbb{R}$ (sin embargo, no sería correcto-continua en $[0,\infty)$ y, a la izquierda continua en $(-\infty,0]$).

Y si no me hacen un error conceptual y utilizamos un equilibrado sistema de numeración (como un El ruso del equipo en la década de 1960) en lugar del sistema decimal, un algoritmo similar (intercambio de 0s y 1s en lugar de 4s y 9s) incluso podría representar una función matemática que es ni siquiera direccional continua en cualquier intervalo de $\mathbb{R}$.

Preguntas:

¿La computabilidad dependen del sistema de numeración que se usa (como en el ejemplo con el equilibrado sistema de numeración sugiere) o es el término "computable" aun suponiendo un cierto sistema de numeración utilizado?

Es la observación correcta de que el término "continuo" no tiene el mismo significado en matemáticas y el CS?

Answer 1

Si usamos la expansión decimal para representar a los números reales, su razonamiento no iba a funcionar.Pero que nos da un muy mal comportamiento noción de computabilidad:

La proposición:La multiplicación por 3 no es computable en relación a la representación decimal.

Prueba:Suponen que la entrada se inicia 0.3333333...En algún momento, nuestro cálculo de necesidades para empezar a producir algo.Las mejores opciones son 0.y 1..En el primer caso, nos ha jodido, si nuestra entrada tiene un 4 como la siguiente dígito que no había mirado;en el segundo caso un 2 nos hace mal.Por lo tanto, no podemos salida de una garantía de un prefijo de la solución.

Utilizando una base diferente daría una noción de computabilidad, pero ninguno de ellos es adecuado.Algunas de las maneras en que todos dan la misma buena noción de computabilidad son:

1. Código real $x$ como una secuencia de racionales $(q_n)_{n \in \mathbb{N}}$ tal que $|x - q_n| < 2^{-n}$.
2. El código de un real a través de una firma de representación dígitos, utilizando $\{-1,0,1\}$.
3. Código real $x$ como una secuencia racional de los intervalos de $(I_n)_{n \in \mathbb{N}}$ con $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

Cuando hablamos de la computabilidad de una función en los reales, sin especificar a qué tipo de representación que estamos utilizando, nos referimos a uno de estos (u otro equivalente).Esto es igual que no siempre podemos señalar el uso de la topología Euclidiana sobre los reales si lo hacemos, ese es justo el caso estándar.Podemos ahora el estado:

Teorema de:Las funciones en los reales que son computables (wrt el estándar de representación) en relación con algunos de oracle son exactamente las funciones continuas (respecto de la topología Euclidiana).

Volviendo al redondeo de las cifras, esto demuestra que perfectamente exacta de redondeo no puede trabajar.Sin embargo, podemos circumvene esto no limitarnos a las funciones.Por ejemplo, la siguiente tarea es computable:

Dado un número real $x \in [0,1]$, de salida , ya sea $0$ o $1$.Si $x < 0.501$, a continuación, $0$ es una solución aceptable y si $x > 0.499$, a continuación, $1$ es una solución aceptable.

Si la entrada a la tarea de arriba es de $[0.499,0.501]$, la respuesta que obtenemos no sólo dependen de la real estamos mirando, pero en el código particular para que real de que nuestro algoritmo lee.Que puede hacer el razonamiento acerca de los algoritmos un poco más engorroso, pero realmente no podemos evitar que.