¿El conjunto de los números computables crecer si fortalecemos nuestro idioma?

Question

Esta podría ser una pregunta tonta, pero ¿puede uno da un ejemplo de un número, que no es computable?

Quiero obtener una imagen mental de lo que estos números reales, de lo que no se puede escribir. Al final de este artículo de la Wikipedia en.wikipedia.org/wiki/Computable_number dice

Para desarrollar el análisis sobre números computables, se debe tener cuidado. Por ejemplo, si se utiliza la definición clásica de una secuencia, el conjunto de los números computables no es cerrado bajo la operación básica de tomar el supremum de un almacén de la secuencia (por ejemplo, considere un Specker secuencia). Esta dificultad se aborda teniendo en cuenta solamente las secuencias que tienen un computable módulo de convergencia. El resultado matemático de la teoría se llama computable análisis.

Lo mismo ocurre con esta decir que uno ha identificado algo uncomputable aquí? Pero si esto es así, no es una descripción de una cosa nos dan una manera de cómputo o el objeto que representa?

Si estamos de paso por paso para siempre fortalecer nuestro idioma, ¿tenemos alguna manera de obtener más números de la serie o $\mathbb R\setminus\mathrm{computable numbers}$? O es que podemos decir "una vez que tenemos un proceso de este y que el poder de computación, podemos calcular ciertos números y nunca más."?

Answer 1

Creo que estás un poco confundir definibles y computable de los números. Tener una "descripción exacta" de un número significa que es definible, pero no necesariamente computable - el supremum de un Specker secuencia y constante de Chaitin(s) son ejemplos de definible, pero no computable números.

A la pregunta de "fortalecimiento de nuestra lengua" tiene alguna relevancia para definability - ver Wikipedia breve discusión sobre definability vs descripción inequívoca.

En términos de la computabilidad las cosas son bastante claramente de corte, ya sea que no hay un algoritmo que calcule el número de precisión arbitraria o no la hay. Cambiar la codificación del algoritmo es irrelevante.

Answer 2

Un no-computable (real) número puede obtenerse a partir de cualquier undecidability resultado, por ejemplo, de la detención Problema. Como un ejemplo, no es un polinomio $P(y,x_1,\dots,x_n)$, con coeficientes enteros, tal que no hay ningún algoritmo que va a determinar, dado un entero no negativo, $y$ como entrada, o si no existen enteros no negativos $x_1,\dots,x_n$ tal que $P(y,x_1,\dots,x_n)=0$. El número real con expansión decimal $0.a_0a_1a_2\dots$ donde $a_i=5$ si $P(a_i,x_1,\dots,x_n)=0$ tiene una solución en enteros no negativos, y $a_i=6$ si no es así, no es computable. Modificación del idioma no alterar eso.

Answer 3

Cualquier número real es el límite de una estrictamente creciente secuencia de racional (como los que son densas) en los reales.

Ahora, cuando la secuencia de $\{q_n\}_{n \in \omega}$ sí es computable (hay un programa que tome $n$ como entrada y salida de $q_n$), el límite todavía no es necesariamente computable.

Hacemos un llamado a los números de "izquierda-computable". Toda la izquierda-computable, los números pueden ser calculadas suponiendo que tenemos el "detener el problema" como un oráculo. En realidad, cuando se elimina el requisito de ser estrictamente creciente para $\{q_n\}_{n \in \omega}$ , el límite de los números de dichas secuencias son exactamente los números uno puede calcular usando la detención problema como un oráculo.

Equivalentemente, que son los números a los que se $\Delta^0_2$, lo que significa que para $X$ de un número, hay dos funciones computables $f$ $g$ tal que

el predicado "|X - p| < p" para $q$ $p$ racionales es equivalente a $\forall n\ \exists m\ f(n, m, q, p)\ \downarrow$, pero también equivalente a $\exists n\ \forall m\ g(n, m, q, p) \ \uparrow$.

Así que sí, el límite de la "Specker secuencia" es un ejemplo de la izquierda-computable, pero no computable número.

Yo no estoy seguro de entender tu última pregunta.