Ejemplo de uncomputable pero definibles por el número de

Question

Cada computable número es definible. Sin embargo, el recíproco no es cierto. ¿Qué es un ejemplo de un número real que es definible , pero que NO es computable? Supongo que si es que hay, se puede "definir" (describa), ¿no?

Answer 1

El punto aquí es que definibles números reales son definibles con toda la fuerza de la fuerza del conjunto teórico del universo; mientras que computable de los números reales, solo se permite el acceso de los números naturales y sus muy muy muy rudimentaria propiedades (desde funciones computables son sólo $\Sigma_1$ funciones ajustables por más de $\Bbb N$).

Deje que $\varphi_n$ enumerar las oraciones en el lenguaje de la aritmética. Ahora, considere el número real cuyo $$n-ésimo dígito en la expansión decimal es de $1$ si y sólo si $\Bbb N\modelos\varphi_n$, y $0$ lo contrario. Así que es un número en $[0,1]$.

Este número es, por supuesto, definible en el lenguaje de la teoría de conjuntos, ya que el conjunto de verdad de oraciones en $\Bbb N$ es definible; pero no es una computable número real ya que no hay computable de la función que nos dice lo que es verdadero en $\Bbb$ N, y lo que no lo es (ni siquiera aritmética, para ser más exactos).

---

También podemos tomar el siguiente método, como comento en el comentario a la pregunta original.

Tenga en cuenta que cada computable real se encuentra en $L$, por el absolutismo de los argumentos (todas las funciones computables se encuentra allí), y en $L$ hay un definibles por el buen orden de los reales (incluso con un $\Delta^1_3$ definición!), así que no es menos real, en la canónica bien ordenar que no es definible.

Desde el conjunto de "los números reales que también se encuentran en $L$" no se puede cambiar entre los modelos de $\sf ZF$ con el mismo ordinales, este conjunto siempre tiene un canónica, definibles por el bien de pedidos en cualquier modelo de $\sf ZF$, y este hecho nos da una definición de un número real que no es computable.

---

También se puede argumentar que varios genéricos reales no son computables, pero definible, si usted está dispuesto a ir tan lejos como para considerar el conjunto diferente de teoría de los universos (o al menos uno, que puede ser visto como un trivial extensión genérica de algunas interior del modelo).

Por ejemplo Jensen reales son definibles (que son la única solución a un $\Pi^1_2$ predicado), pero no computable.

Del mismo modo, se puede considerar que las obligando a afirmar que en el $$n-ésimo paso realiza la lotería de la suma entre obligando a $2^{\aleph_n}=\aleph_{n+1}$ y obligando a los $2^{\aleph_n}=\aleph_{n+2}$, en el límite de paso tomar un número finito de apoyo límite, y consideran que el número real cuyo $$n-ésimo dígito decimal $1$ si y sólo si $2^{\aleph_n}=\aleph_{n+1}$ y $0$ lo contrario.

Este es un Cohen real que es definible, ya que codifica la continuidad por debajo de $\aleph_\omega$; pero, por supuesto, no es computable por genericity argumentos.

Tenga en cuenta que esto da una muy peculiar ejemplo de un número real, una codificación de la continuidad de la función por debajo de $\aleph_\omega$. Siempre es definible, pero en diferentes modelos de $\sf ZFC$ duraran tener valores diferentes, a veces les será computable (por ejemplo, si $\sf GCH$ tiene) y, a veces, que podría ser no-computable (como arriba).

Así que esto nos da una definición de un número real que no es demostrablemente computable y no se puede probar uncomputable!

Answer 2

Aquí es un no-computable número real: $$\sum_{i=1}^\infty 2^{-\Sigma(i)}$$ donde $\Sigma$ es cualquier busy beaver función.

Answer 3

La probabilidad de que un equipo al azar programa se ejecutará para siempre no es computable. http://en.wikipedia.org/wiki/Chaitin%27s_constant

Que algunos aspectos de nuestros conceptos en esta área son problemáticos se ilustra en el siguiente ejemplo, que he aprendido de Hartley Rogers' libro de la computabilidad: vamos a $$ f(x) = \begin{casos} 1 & \text{si hay una secuencia de }x\text{ consecutivos 7s en la expansión decimal de }\pi, \\ 0 & \text{en caso contrario}. \end{casos} $$ Este es computable! Y no es un argumento fácil para su computabilidad. Y el algoritmo para el cálculo de esta función es realmente muy simple. Se puede demostrar fácilmente, pero nadie sabe, ni es en absoluto fácil, a saber, que el algoritmo es.

Answer 4

Si consideramos una enumeración de todos los posibles pares de máquinas de turing y las entradas, entonces podemos permitir $$ S denota el conjunto de los enteros positivos $$ n para que el $n$th par detiene. Ahora este número $x$ será bien definido, pero uncomputable:

$$x = \frac 1 3 + 4\sum_{n \in S} 10^{-n}$$

$x$ se componen de una secuencia de decimales todos de los cuales son 3 o 7. El $n$th decimal será de 7 si $n$th par de la máquina de turing y de entrada se detiene, y 3 de otro modo. En otras palabras, el cómputo decimal de $x$ es equivalente a la resolución de una instancia de la detención problema.

Lo que también es interesante alrededor de $x$ es que no es un simple algoritmo constructivo para producir una secuencia de números racionales, que convergen hacia la $x$.

• Inicializar $a := \frac 1 3$
• Para $i \in \mathbb{N}$ hacer:
  • Simular los primeros $i$ máquinas de turing por primera $i$ pasos.
  • Para cada máquina de turing $n$, que se detuvo y no se detiene para cualquier menor de $i$:
    • $a := a + 4 \cdot 10 ^{-n}$
    • Salida $$

Esto muestra que es posible para una computable de la secuencia de los números racionales a converger en un no-computable número. Esto es un poco más de lo que usted solicitó, pero para mí este ejemplo en particular me dio una mejor idea de lo que el límite de compatibilidad parece.

Answer 5

La constante de Chaitin es un número bien definido en la teoría de la computabilidad, pero no es computable. Pero, sobre el concepto de definibles por el número de ver las respuestas a Definibles de los números reales.