Hay ejemplos de no-computable de los números reales?

Question

Es esto cierto, que si podemos describir cualquier (real) número de alguna manera, entonces es computable?

Por ejemplo, $\pi$ es computable a pesar de que es irracional, es decir, un sinfín fracción decimal. Era sólo un poco de suerte, que hay algunos periódica simple fórmulas para calcualte $\pi$. Si no fuera que no hemos podido calcular $\pi$ ans fue no-computable.

Si es así, que no podemos dar algunos ejemplos de no-computable números? Es ese derecho?

La única cosa que podemos decir es que estos números son los que existen en muchos, pero no podemos señalar a ninguno de ellos. A la derecha?

Answer 1

No he pensado, pero me parece que si vamos a $BB$ ser el Busy Beaver función, $$\sum_{i=1}^\infty 2^{-BB(i)}=2^{-1}+2^{-6}+2^{-21}+2^{-107}+\ ... \ \approx 0.515625476837158203125000000000006$ $ debe ser un noncomputable número real, ya que si fueron capaces de calcular con suficiente precisión que usted sería capaz de resolver la paralización problema.

Answer 2

Chaitin es constante, es un ejemplo (en realidad una familia de ejemplos) de un noncomputable número. Representa la probabilidad de que una al azar generados por el programa (en un determinado modelo) va a detener.

Se puede calcular aproximadamente, pero no es (seguramente) no hay algoritmo para calcular con precisión arbitraria.

Answer 3

Cualquier idioma puede convertirse en un número, por la configuración de la $i^{th}$ decimal a 1 si el $i^{th}$ palabra está en el lenguaje, y 0 en caso contrario. Así que podemos construir, por ejemplo, el número de $H$, que describe la detención problema y es por lo tanto uncomputable.