un número real "natural" no computable

Question

La mayoría de los ejemplos de números reales no computables utilizan algún tipo de construcción de diagonalización sobre algún modelo de computación computable en turing. Véase ¿Existen ejemplos de números reales no computables? .

Quiero saber si existen números reales "naturales" que no sean computables. Tengo dificultades para formalizar lo que entiendo por "natural". He aquí una condición necesaria para la naturalidad: La descripción de ese número no debe mencionar ningún modelo computable turing de computación.

Idealmente, este número debería haber existido en la literatura incluso antes de que Turing inventara las máquinas de Turing. De alguna manera esto es análogo a la forma en que Solomon Feferman dice:

Por último, hay que tener en cuenta que hasta ahora no se conoce ningún problema abierto de la teoría de números o de la combinatoria finita, como la conjetura de Goldbach o la hipótesis de Riemann o la conjetura de los primos gemelos o el problema P=NP, que haya sido formulado con anterioridad (desde el día en que Gödel anunció sus teoremas de incompletitud) y que sea independiente de los tipos de sistemas formales de los que hemos estado hablando, ni siquiera de PA.

en http://math.stanford.edu/~feferman/papers/newaxioms.pdf . Las partes entre paréntesis las he añadido yo para situar su cita en el contexto adecuado. Mi pregunta estaba motivada en parte por esta cita.

Answer 1

La intuición correcta es que no hay ejemplos de particular números reales naturales no computables.

Un obstáculo importante para encontrar un ejemplo es que la computabilidad trata más directamente de conjuntos de naturales, no de números reales. La mayoría de los ejemplos de números reales no computables se construyen codificando un conjunto no computable de naturales en un número real. El método de codificación es siempre algo arbitrario, lo que va en contra de la unicidad del número real que se construye.

Ejemplos de métodos de codificación

He aquí dos ejemplos de distintos métodos de codificación. El problema es que la mejor forma de codificar información en un número real parece ser utilizar de alguna manera la expansión decimal (o binaria, o de base 813), pero no existe una forma "canónica" o "mejor" obvia de hacerlo. Supongamos que tenemos un conjunto infinito $A$ de números naturales. Puedo hacer un número real $r$ que "computa" $A$ de varias maneras:

• Puedo hacer que $r \in [0,1]$ y la expansión decimal de $r$ es la función característica de $A$ . También podría hacerlo para que $r \in [0,1]$ y la expansión binaria de $r$ es la función característica de $A$ . Ninguno de los dos parece más canónico que el otro.

• Puedo hacer que los "huecos" entre los dígitos distintos de cero en la expansión binaria de $r$ Háblame de $A$ . Así que si $A = \{1, 3, 5, \ldots\}$ entonces tomo $$ r = 0.1010001000001\ldots$$

Answer 2

No conozco ningún número conocido que no sea computable, pero se puede construir fácilmente uno que no implique ninguna máquina de Turing ni ninguna otra forma similar de computación (p. ej. $\lambda$ -términos, gramáticas, etc.).

Para dar un ejemplo, eche un vistazo a Lista de problemas indecidibles de Wikipedia y elige uno que te guste.

Por ejemplo, podríamos tomar el problema de la mortalidad matricial y convertir las entradas en una secuencia, por ejemplo, elige tu biyección favorita $\mathbb{N} \to \mathbb{Z}^{2\cdot 15^2}$ y crear una secuencia $(a_n)_{n \in \mathbb{N}}$ de pares de números enteros $15 \times 15$ matrices. Entonces definimos $f : M_{15\times 15} \times M_{15\times 15} \to \{0,1\}$ como $f(A,B) = 1$ si existe $k \in \mathbb{N}$ y función $h : \{0,..,k\} \to \{A,B\}$ tal que $\prod_{i = 0}^k h(i) = \mathbf{0}$ y $f(A,B) = 0$ de lo contrario.

Ahora podemos definir nuestro número como $$\sum_{k \in \mathbb{N}}\frac{f(a_k)}{2^k}$$

y porque el problema de la mortalidad matricial es indecidible entonces el número anterior es incalculable.

Sé que esto no es exactamente lo que estabas buscando, pero tal vez pueda ayudarte $\ddot\smile$