Son algunos de los números reales "uncomputable"?

Question

Existe un algoritmo para calcular cualquier número real. Me refiero a dado $a \in \mathbb{R}$ es que hay un algoritmo para calcular $$ en cualquier grado de precisión ?

Leí en algún sitio (no puedo encontrar el papel) que la respuesta es no, debido a que $\mathbb{R}$ no es un conjunto recursivo ya que no es una contables conjunto.

Pero me falta algo... me puede alguien explicar en detalle por qué así ?

Por otra parte, significa que existe un número real que se uncomputable, y que no se puede ni escribir, ni expresar... es como si no existieran.

Answer 1

Como usted ha observado usted, $\mathbb{R}$, el conjunto de los números reales, es incontable, pero cada recursivamente enumerable conjunto es necesariamente contables. Esto implica inmediatamente que existen uncomputable los números reales. El mismo argumento muestra que hay (formalmente) indescriptible números reales. De hecho, casi todos los números reales son indescriptibles, y a fortiori, uncomputable. No hay nada de malo en esto, aunque puede ser perturbador.

Hacer uncomputable/indescriptible números reales "existe"? Bueno, esa es una pregunta filosófica. Un Platónico podría decir que existen, aunque no tenemos forma de nombrar específicamente a ellos. Un finitist podría decir que no existe, precisamente porque tenemos ningún algoritmo para calcular o incluso reconocer a dicho número.

Afecta esto a la forma de hacer matemáticas? De verdad que no. Entonces, ¿qué si la gran mayoría de los números reales son uncomputable? Por lo general, nos lidiar con el genérico de los números reales, no específicos. Por ejemplo, el hecho de que todos los no-cero número real $x$ tiene una inversa no depende de la computabilidad propiedades de $x$.

Answer 2

La mayoría de los números reales son no computables. Informalmente hablando, un número real es computable si existe una máquina o de un algoritmo que calcula su expansión decimal, un dígito a la vez, es decir, usted puede pedir los $$n-ésimo dígito. Una vez que formalizar máquinas y algoritmos, que son finitos los animales, se ve que sólo hay una contables número de ellos y tan sólo hay un contable número computable de los números reales. Puesto que los números reales no son numerables, la mayoría de los números reales no son computables.

Answer 3

Sí, usted puede calcular $$ hasta arbitrariamente un pequeño error. Pero si usted quiere encontrar la descripción exacta, usted será capaz de hacer esto sólo para una contables conjunto de números. Por ejemplo, cada descripción de un número contiene un conjunto finito de palabras, y así el conjunto de todas estas descripciones es contable. Desde el conjunto de todos los números reales no es contable, muchos números reales no puede ser descrito, sólo sabemos que existen.

Answer 4

Precisamente, un número real $x$ es computable si existe un total computable de la función $\varphi_{e}$ tal que $|x-q_{\varphi_{e}(n)}|<2^{n}$, donde $\langle q_i \rangle_{i \in \omega}$ es un eficaz numeración de los racionales. Por lo que $\varphi_{e}$ recoge a un computably rápida convergencia de la secuencia de racionales cuyo límite es de $x$. Tenga en cuenta que uno puede entonces calcular la expansión decimal de $x$ para cualquier precisión deseada (y sabe que la precisión se ha alcanzado).

Desde cada $\varphi_{e}$ corresponde a más de un computable real y sólo hay countably muchos de esos $\varphi_{e}$'s, no puede haber más de countably muchos computable de reales. Por supuesto, cada racional es computable, por lo que hay un infinito contable computables de reales.

Respecto a su comentario: "...es como que no existe". Aquí usted tiene que entender lo que significa para algo existen en las matemáticas o—mejor aún—en la lógica de primer orden. El punto es que una vez que se conoce el conjunto de números computables es contable, Cantor de la diagonal argumento puede ser llevado a cabo en ZFC para mostrar que no hay surjection de los números computables en todos los reales; es decir, noncomputable números deben "existir".